summaryrefslogtreecommitdiff
path: root/compiler
diff options
context:
space:
mode:
Diffstat (limited to 'compiler')
-rw-r--r--compiler/optimizing/bounds_check_elimination_test.cc327
-rw-r--r--compiler/optimizing/induction_var_analysis_test.cc82
-rw-r--r--compiler/optimizing/induction_var_range_test.cc48
-rw-r--r--compiler/optimizing/load_store_elimination_test.cc473
-rw-r--r--compiler/optimizing/optimizing_unit_test.h70
-rw-r--r--compiler/optimizing/superblock_cloner_test.cc212
6 files changed, 338 insertions, 874 deletions
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 5ddd25335b..05bd35dbc7 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -35,13 +35,8 @@ namespace art HIDDEN {
*/
class BoundsCheckEliminationTest : public OptimizingUnitTest {
public:
- BoundsCheckEliminationTest() : graph_(CreateGraph()) {
- graph_->SetHasBoundsChecks(true);
- }
-
- ~BoundsCheckEliminationTest() { }
-
void RunBCE() {
+ graph_->SetHasBoundsChecks(true);
graph_->BuildDominatorTree();
InstructionSimplifier(graph_, /* codegen= */ nullptr).Run();
@@ -61,8 +56,6 @@ class BoundsCheckEliminationTest : public OptimizingUnitTest {
HInstruction* BuildSSAGraph2(int initial, int increment = -1, IfCondition cond = kCondLE);
HInstruction* BuildSSAGraph3(int initial, int increment, IfCondition cond);
HInstruction* BuildSSAGraph4(int initial, IfCondition cond = kCondGE);
-
- HGraph* graph_;
};
@@ -70,8 +63,8 @@ class BoundsCheckEliminationTest : public OptimizingUnitTest {
// else if (i >= array.length) { array[i] = 1; // Can't eliminate. }
// else { array[i] = 1; // Can eliminate. }
TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) {
- HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry);
+ CreateGraph();
+ HBasicBlock* entry = AddNewBlock();
graph_->SetEntryBlock(entry);
HInstruction* parameter1 = MakeParam(DataType::Type::kReference); // array
HInstruction* parameter2 = MakeParam(DataType::Type::kInt32); // i
@@ -79,42 +72,36 @@ TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) {
HInstruction* constant_1 = graph_->GetIntConstant(1);
HInstruction* constant_0 = graph_->GetIntConstant(0);
- HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block1);
+ HBasicBlock* block1 = AddNewBlock();
HInstruction* cmp = MakeCondition<HGreaterThanOrEqual>(block1, parameter2, constant_0);
MakeIf(block1, cmp);
entry->AddSuccessor(block1);
- HBasicBlock* block2 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block2);
+ HBasicBlock* block2 = AddNewBlock();
HNullCheck* null_check = MakeNullCheck(block2, parameter1);
HArrayLength* array_length = MakeArrayLength(block2, null_check);
HBoundsCheck* bounds_check2 = MakeBoundsCheck(block2, parameter2, array_length);
MakeArraySet(block2, null_check, bounds_check2, constant_1, DataType::Type::kInt32);
- HBasicBlock* block3 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block3);
+ HBasicBlock* block3 = AddNewBlock();
null_check = MakeNullCheck(block3, parameter1);
array_length = MakeArrayLength(block3, null_check);
cmp = MakeCondition<HLessThan>(block3, parameter2, array_length);
MakeIf(block3, cmp);
- HBasicBlock* block4 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block4);
+ HBasicBlock* block4 = AddNewBlock();
null_check = MakeNullCheck(block4, parameter1);
array_length = MakeArrayLength(block4, null_check);
HBoundsCheck* bounds_check4 = MakeBoundsCheck(block4, parameter2, array_length);
MakeArraySet(block4, null_check, bounds_check4, constant_1, DataType::Type::kInt32);
- HBasicBlock* block5 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block5);
+ HBasicBlock* block5 = AddNewBlock();
null_check = MakeNullCheck(block5, parameter1);
array_length = MakeArrayLength(block5, null_check);
HBoundsCheck* bounds_check5 = MakeBoundsCheck(block5, parameter2, array_length);
MakeArraySet(block5, null_check, bounds_check5, constant_1, DataType::Type::kInt32);
- HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(exit);
+ HBasicBlock* exit = AddNewBlock();
block2->AddSuccessor(exit);
block4->AddSuccessor(exit);
block5->AddSuccessor(exit);
@@ -139,8 +126,8 @@ TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) {
// if (j < array.length) array[j] = 1; // Can't eliminate.
// }
TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) {
- HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry);
+ CreateGraph();
+ HBasicBlock* entry = AddNewBlock();
graph_->SetEntryBlock(entry);
HInstruction* parameter1 = MakeParam(DataType::Type::kReference); // array
HInstruction* parameter2 = MakeParam(DataType::Type::kInt32); // i
@@ -149,27 +136,23 @@ TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) {
HInstruction* constant_0 = graph_->GetIntConstant(0);
HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
- HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block1);
+ HBasicBlock* block1 = AddNewBlock();
HInstruction* cmp = MakeCondition<HLessThanOrEqual>(block1, parameter2, constant_0);
MakeIf(block1, cmp);
entry->AddSuccessor(block1);
- HBasicBlock* block2 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block2);
+ HBasicBlock* block2 = AddNewBlock();
HInstruction* add = MakeBinOp<HAdd>(block2, DataType::Type::kInt32, parameter2, constant_max_int);
HNullCheck* null_check = MakeNullCheck(block2, parameter1);
HArrayLength* array_length = MakeArrayLength(block2, null_check);
HInstruction* cmp2 = MakeCondition<HGreaterThanOrEqual>(block2, add, array_length);
MakeIf(block2, cmp2);
- HBasicBlock* block3 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block3);
+ HBasicBlock* block3 = AddNewBlock();
HBoundsCheck* bounds_check = MakeBoundsCheck(block3, add, array_length);
MakeArraySet(block3, null_check, bounds_check, constant_1, DataType::Type::kInt32);
- HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(exit);
+ HBasicBlock* exit = AddNewBlock();
MakeExit(exit);
block1->AddSuccessor(exit); // true successor
block1->AddSuccessor(block2); // false successor
@@ -188,8 +171,8 @@ TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) {
// if (j > 0) array[j] = 1; // Can't eliminate.
// }
TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
- HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry);
+ CreateGraph();
+ HBasicBlock* entry = AddNewBlock();
graph_->SetEntryBlock(entry);
HInstruction* parameter1 = MakeParam(DataType::Type::kReference); // array
HInstruction* parameter2 = MakeParam(DataType::Type::kInt32); // i
@@ -198,29 +181,25 @@ TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
HInstruction* constant_0 = graph_->GetIntConstant(0);
HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
- HBasicBlock* block1 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block1);
+ HBasicBlock* block1 = AddNewBlock();
HNullCheck* null_check = MakeNullCheck(block1, parameter1);
HArrayLength* array_length = MakeArrayLength(block1, null_check);
HInstruction* cmp = MakeCondition<HGreaterThanOrEqual>(block1, parameter2, array_length);
MakeIf(block1, cmp);
entry->AddSuccessor(block1);
- HBasicBlock* block2 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block2);
+ HBasicBlock* block2 = AddNewBlock();
HInstruction* sub1 =
MakeBinOp<HSub>(block2, DataType::Type::kInt32, parameter2, constant_max_int);
HInstruction* sub2 = MakeBinOp<HSub>(block2, DataType::Type::kInt32, sub1, constant_max_int);
HInstruction* cmp2 = MakeCondition<HLessThanOrEqual>(block2, sub2, constant_0);
MakeIf(block2, cmp2);
- HBasicBlock* block3 = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block3);
+ HBasicBlock* block3 = AddNewBlock();
HBoundsCheck* bounds_check = MakeBoundsCheck(block3, sub2, array_length);
MakeArraySet(block3, null_check, bounds_check, constant_1, DataType::Type::kInt32);
- HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(exit);
+ HBasicBlock* exit = AddNewBlock();
MakeExit(exit);
block1->AddSuccessor(exit); // true successor
block1->AddSuccessor(block2); // false successor
@@ -237,20 +216,14 @@ TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
// array[5] = 1; // Can eliminate.
// array[4] = 1; // Can eliminate.
TEST_F(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
- HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry);
- graph_->SetEntryBlock(entry);
- HInstruction* parameter = MakeParam(DataType::Type::kReference);
+ HBasicBlock* block = InitEntryMainExitGraphWithReturnVoid();
+ HInstruction* parameter = MakeParam(DataType::Type::kReference);
HInstruction* constant_5 = graph_->GetIntConstant(5);
HInstruction* constant_4 = graph_->GetIntConstant(4);
HInstruction* constant_6 = graph_->GetIntConstant(6);
HInstruction* constant_1 = graph_->GetIntConstant(1);
- HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block);
- entry->AddSuccessor(block);
-
HNullCheck* null_check = MakeNullCheck(block, parameter);
HArrayLength* array_length = MakeArrayLength(block, null_check);
HBoundsCheck* bounds_check6 = MakeBoundsCheck(block, constant_6, array_length);
@@ -266,13 +239,6 @@ TEST_F(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
HBoundsCheck* bounds_check4 = MakeBoundsCheck(block, constant_4, array_length);
MakeArraySet(block, null_check, bounds_check4, constant_1, DataType::Type::kInt32);
- MakeGoto(block);
-
- HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(exit);
- block->AddSuccessor(exit);
- MakeExit(exit);
-
RunBCE();
ASSERT_FALSE(IsRemoved(bounds_check6));
@@ -284,33 +250,13 @@ TEST_F(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
HInstruction* BoundsCheckEliminationTest::BuildSSAGraph1(int initial,
int increment,
IfCondition cond) {
- HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry);
- graph_->SetEntryBlock(entry);
- HInstruction* parameter = MakeParam(DataType::Type::kReference);
+ HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
+ auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
- HInstruction* constant_initial = graph_->GetIntConstant(initial);
- HInstruction* constant_increment = graph_->GetIntConstant(increment);
+ HInstruction* parameter = MakeParam(DataType::Type::kReference);
HInstruction* constant_10 = graph_->GetIntConstant(10);
- HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block);
- entry->AddSuccessor(block);
- MakeGoto(block);
-
- HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
-
- graph_->AddBlock(loop_header);
- graph_->AddBlock(loop_body);
- graph_->AddBlock(exit);
- block->AddSuccessor(loop_header);
- loop_header->AddSuccessor(exit); // true successor
- loop_header->AddSuccessor(loop_body); // false successor
- loop_body->AddSuccessor(loop_header);
-
- HPhi* phi = MakePhi(loop_header, {constant_initial, /* placeholder */ constant_initial});
+ auto [phi, add] = MakeLinearLoopVar(loop_header, loop_body, initial, increment);
HInstruction* null_check = MakeNullCheck(loop_header, parameter);
HInstruction* array_length = MakeArrayLength(loop_header, null_check);
HInstruction* cmp = nullptr;
@@ -326,12 +272,6 @@ HInstruction* BoundsCheckEliminationTest::BuildSSAGraph1(int initial,
array_length = MakeArrayLength(loop_body, null_check);
HInstruction* bounds_check = MakeBoundsCheck(loop_body, phi, array_length);
MakeArraySet(loop_body, null_check, bounds_check, constant_10, DataType::Type::kInt32);
- HInstruction* add = MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, phi, constant_increment);
- MakeGoto(loop_body);
-
- phi->ReplaceInput(add, 1u); // Update back-edge input.
-
- MakeExit(exit);
return bounds_check;
}
@@ -383,36 +323,19 @@ TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1f) {
HInstruction* BoundsCheckEliminationTest::BuildSSAGraph2(int initial,
int increment,
IfCondition cond) {
- HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry);
- graph_->SetEntryBlock(entry);
- HInstruction* parameter = MakeParam(DataType::Type::kReference);
+ HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
+ auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
+ HInstruction* parameter = MakeParam(DataType::Type::kReference);
HInstruction* constant_initial = graph_->GetIntConstant(initial);
HInstruction* constant_increment = graph_->GetIntConstant(increment);
HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
HInstruction* constant_10 = graph_->GetIntConstant(10);
- HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block);
- entry->AddSuccessor(block);
- HInstruction* null_check = MakeNullCheck(block, parameter);
- HInstruction* array_length = MakeArrayLength(block, null_check);
- MakeGoto(block);
-
- HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
-
- graph_->AddBlock(loop_header);
- graph_->AddBlock(loop_body);
- graph_->AddBlock(exit);
- block->AddSuccessor(loop_header);
- loop_header->AddSuccessor(exit); // true successor
- loop_header->AddSuccessor(loop_body); // false successor
- loop_body->AddSuccessor(loop_header);
-
- HPhi* phi = MakePhi(loop_header, {array_length, /* placeholder */ array_length});
+ HInstruction* null_check = MakeNullCheck(pre_header, parameter);
+ HInstruction* array_length = MakeArrayLength(pre_header, null_check);
+
+ auto [phi, add] = MakeLinearLoopVar(loop_header, loop_body, array_length, constant_minus_1);
HInstruction* cmp = nullptr;
if (cond == kCondLE) {
cmp = MakeCondition<HLessThanOrEqual>(loop_header, phi, constant_initial);
@@ -422,17 +345,10 @@ HInstruction* BoundsCheckEliminationTest::BuildSSAGraph2(int initial,
}
MakeIf(loop_header, cmp);
- HInstruction* add = MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, phi, constant_minus_1);
null_check = MakeNullCheck(loop_body, parameter);
array_length = MakeArrayLength(loop_body, null_check);
HInstruction* bounds_check = MakeBoundsCheck(loop_body, add, array_length);
MakeArraySet(loop_body, null_check, bounds_check, constant_10, DataType::Type::kInt32);
- MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, phi, constant_increment);
- MakeGoto(loop_body);
-
- phi->ReplaceInput(add, 1u); // Update back-edge input.
-
- MakeExit(exit);
return bounds_check;
}
@@ -477,34 +393,16 @@ TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2e) {
HInstruction* BoundsCheckEliminationTest::BuildSSAGraph3(int initial,
int increment,
IfCondition cond) {
- HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry);
- graph_->SetEntryBlock(entry);
+ HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
+ auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
HInstruction* constant_10 = graph_->GetIntConstant(10);
- HInstruction* constant_initial = graph_->GetIntConstant(initial);
- HInstruction* constant_increment = graph_->GetIntConstant(increment);
- HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block);
- entry->AddSuccessor(block);
// We pass a bogus constant for the class to avoid mocking one.
- HInstruction* new_array = MakeNewArray(block, /* cls= */ constant_10, /* length= */ constant_10);
- MakeGoto(block);
-
- HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
-
- graph_->AddBlock(loop_header);
- graph_->AddBlock(loop_body);
- graph_->AddBlock(exit);
- block->AddSuccessor(loop_header);
- loop_header->AddSuccessor(exit); // true successor
- loop_header->AddSuccessor(loop_body); // false successor
- loop_body->AddSuccessor(loop_header);
-
- HPhi* phi = MakePhi(loop_header, {constant_initial, /* placeholder */ constant_initial});
+ HInstruction* new_array =
+ MakeNewArray(pre_header, /* cls= */ constant_10, /* length= */ constant_10);
+
+ auto [phi, add] = MakeLinearLoopVar(loop_header, loop_body, initial, increment);
HInstruction* cmp = nullptr;
if (cond == kCondGE) {
cmp = MakeCondition<HGreaterThanOrEqual>(loop_header, phi, constant_10);
@@ -518,12 +416,6 @@ HInstruction* BoundsCheckEliminationTest::BuildSSAGraph3(int initial,
HArrayLength* array_length = MakeArrayLength(loop_body, null_check);
HInstruction* bounds_check = MakeBoundsCheck(loop_body, phi, array_length);
MakeArraySet(loop_body, null_check, bounds_check, constant_10, DataType::Type::kInt32);
- HInstruction* add = MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, phi, constant_increment);
- MakeGoto(loop_body);
-
- phi->ReplaceInput(add, 1u); // Update back-edge input.
-
- MakeExit(exit);
return bounds_check;
}
@@ -562,34 +454,14 @@ TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) {
// for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; }
HInstruction* BoundsCheckEliminationTest::BuildSSAGraph4(int initial, IfCondition cond) {
- HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry);
- graph_->SetEntryBlock(entry);
- HInstruction* parameter = MakeParam(DataType::Type::kReference);
+ HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
+ auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
- HInstruction* constant_initial = graph_->GetIntConstant(initial);
- HInstruction* constant_1 = graph_->GetIntConstant(1);
+ HInstruction* parameter = MakeParam(DataType::Type::kReference);
HInstruction* constant_10 = graph_->GetIntConstant(10);
HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
- HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block);
- entry->AddSuccessor(block);
- MakeGoto(block);
-
- HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
-
- graph_->AddBlock(loop_header);
- graph_->AddBlock(loop_body);
- graph_->AddBlock(exit);
- block->AddSuccessor(loop_header);
- loop_header->AddSuccessor(exit); // true successor
- loop_header->AddSuccessor(loop_body); // false successor
- loop_body->AddSuccessor(loop_header);
-
- HPhi* phi = MakePhi(loop_header, {constant_initial, /* placeholder */ constant_initial});
+ auto [phi, add] = MakeLinearLoopVar(loop_header, loop_body, initial, /*increment=*/ 1);
HInstruction* null_check = MakeNullCheck(loop_header, parameter);
HInstruction* array_length = MakeArrayLength(loop_header, null_check);
HInstruction* cmp = nullptr;
@@ -608,12 +480,6 @@ HInstruction* BoundsCheckEliminationTest::BuildSSAGraph4(int initial, IfConditio
MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, sub, constant_minus_1);
HInstruction* bounds_check = MakeBoundsCheck(loop_body, add_minus_1, array_length);
MakeArraySet(loop_body, null_check, bounds_check, constant_10, DataType::Type::kInt32);
- HInstruction* add = MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, phi, constant_1);
- MakeGoto(loop_body);
-
- phi->ReplaceInput(add, 1u); // Update back-edge input.
-
- MakeExit(exit);
return bounds_check;
}
@@ -642,45 +508,35 @@ TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) {
// Bubble sort:
// (Every array access bounds-check can be eliminated.)
// for (int i=0; i<array.length-1; i++) {
-// for (int j=0; j<array.length-i-1; j++) {
+// for (int j=0; j<array.length-i-1; j++) {
// if (array[j] > array[j+1]) {
// int temp = array[j+1];
// array[j+1] = array[j];
// array[j] = temp;
// }
-// }
+// }
// }
TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
- HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry);
- graph_->SetEntryBlock(entry);
- HInstruction* parameter = MakeParam(DataType::Type::kReference);
+ HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
+ auto [outer_pre_header, outer_header, outer_body_add] = CreateWhileLoop(return_block);
+ auto [inner_pre_header, inner_header, inner_body_add] = CreateWhileLoop(outer_body_add);
+ auto [inner_body_compare, inner_body_swap, skip_swap] = CreateDiamondPattern(inner_body_add);
+ HInstruction* parameter = MakeParam(DataType::Type::kReference);
HInstruction* constant_0 = graph_->GetIntConstant(0);
HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
HInstruction* constant_1 = graph_->GetIntConstant(1);
- HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block);
- entry->AddSuccessor(block);
- MakeGoto(block);
-
- HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(exit);
- MakeExit(exit);
-
- HBasicBlock* outer_header = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(outer_header);
- HPhi* phi_i = MakePhi(outer_header, {constant_0, /* placeholder */ constant_0});
+ auto [phi_i, add_i] =
+ MakeLinearLoopVar(outer_header, outer_body_add, /*initial=*/ 0, /*increment=*/ 1);
HNullCheck* null_check = MakeNullCheck(outer_header, parameter);
HArrayLength* array_length = MakeArrayLength(outer_header, null_check);
HAdd* add = MakeBinOp<HAdd>(outer_header, DataType::Type::kInt32, array_length, constant_minus_1);
HInstruction* cmp = MakeCondition<HGreaterThanOrEqual>(outer_header, phi_i, add);
MakeIf(outer_header, cmp);
- HBasicBlock* inner_header = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(inner_header);
- HPhi* phi_j = MakePhi(inner_header, {constant_0, /* placeholder */ constant_0});
+ auto [phi_j, add_j] =
+ MakeLinearLoopVar(inner_header, inner_body_add, /*initial=*/ 0, /*increment=*/ 1);
null_check = MakeNullCheck(inner_header, parameter);
array_length = MakeArrayLength(inner_header, null_check);
HSub* sub = MakeBinOp<HSub>(inner_header, DataType::Type::kInt32, array_length, phi_i);
@@ -688,8 +544,6 @@ TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
cmp = MakeCondition<HGreaterThanOrEqual>(inner_header, phi_j, add);
MakeIf(inner_header, cmp);
- HBasicBlock* inner_body_compare = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(inner_body_compare);
null_check = MakeNullCheck(inner_body_compare, parameter);
array_length = MakeArrayLength(inner_body_compare, null_check);
HBoundsCheck* bounds_check1 = MakeBoundsCheck(inner_body_compare, phi_j, array_length);
@@ -705,8 +559,6 @@ TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
cmp = MakeCondition<HGreaterThanOrEqual>(inner_body_compare, array_get_j, array_get_j_plus_1);
MakeIf(inner_body_compare, cmp);
- HBasicBlock* inner_body_swap = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(inner_body_swap);
j_plus_1 = MakeBinOp<HAdd>(inner_body_swap, DataType::Type::kInt32, phi_j, constant_1);
// temp = array[j+1]
null_check = MakeNullCheck(inner_body_swap, parameter);
@@ -729,32 +581,6 @@ TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
HInstruction* bounds_check6 = MakeBoundsCheck(inner_body_swap, phi_j, array_length);
MakeArraySet(
inner_body_swap, null_check, bounds_check6, array_get_j_plus_1, DataType::Type::kInt32);
- MakeGoto(inner_body_swap);
-
- HBasicBlock* inner_body_add = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(inner_body_add);
- add = MakeBinOp<HAdd>(inner_body_add, DataType::Type::kInt32, phi_j, constant_1);
- MakeGoto(inner_body_add);
-
- phi_j->ReplaceInput(add, 1u); // Update back-edge input.
-
- HBasicBlock* outer_body_add = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(outer_body_add);
- add = MakeBinOp<HAdd>(outer_body_add, DataType::Type::kInt32, phi_i, constant_1);
- MakeGoto(outer_body_add);
-
- phi_i->ReplaceInput(add, 1u); // Update back-edge input.
-
- block->AddSuccessor(outer_header);
- outer_header->AddSuccessor(exit);
- outer_header->AddSuccessor(inner_header);
- inner_header->AddSuccessor(outer_body_add);
- inner_header->AddSuccessor(inner_body_compare);
- inner_body_compare->AddSuccessor(inner_body_add);
- inner_body_compare->AddSuccessor(inner_body_swap);
- inner_body_swap->AddSuccessor(inner_body_add);
- inner_body_add->AddSuccessor(inner_header);
- outer_body_add->AddSuccessor(outer_header);
RunBCE(); // gvn removes same bounds check already
@@ -776,37 +602,20 @@ TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
// array[param_i%10] = 10; // Can't eliminate, when param_i < 0
// }
TEST_F(BoundsCheckEliminationTest, ModArrayBoundsElimination) {
- HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry);
- graph_->SetEntryBlock(entry);
- HInstruction* param_i = MakeParam(DataType::Type::kInt32);
+ HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
+ auto [pre_header, loop_header, loop_body] = CreateWhileLoop(return_block);
- HInstruction* constant_0 = graph_->GetIntConstant(0);
+ HInstruction* param_i = MakeParam(DataType::Type::kInt32);
HInstruction* constant_1 = graph_->GetIntConstant(1);
HInstruction* constant_10 = graph_->GetIntConstant(10);
HInstruction* constant_200 = graph_->GetIntConstant(200);
HInstruction* constant_minus_10 = graph_->GetIntConstant(-10);
- HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(block);
- entry->AddSuccessor(block);
// We pass a bogus constant for the class to avoid mocking one.
- HInstruction* new_array = MakeNewArray(block, /* cls= */ constant_10, /* length= */ constant_10);
- MakeGoto(block);
-
- HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph_);
-
- graph_->AddBlock(loop_header);
- graph_->AddBlock(loop_body);
- graph_->AddBlock(exit);
- block->AddSuccessor(loop_header);
- loop_header->AddSuccessor(exit); // true successor
- loop_header->AddSuccessor(loop_body); // false successor
- loop_body->AddSuccessor(loop_header);
-
- HPhi* phi = MakePhi(loop_header, {constant_0, /* placeholder */ constant_0});
+ HInstruction* new_array =
+ MakeNewArray(pre_header, /* cls= */ constant_10, /* length= */ constant_10);
+
+ auto [phi, add] = MakeLinearLoopVar(loop_header, loop_body, /*initial=*/ 0, /*increment=*/ 1);
HInstruction* cmp = MakeCondition<HGreaterThanOrEqual>(loop_header, phi, constant_200);
MakeIf(loop_header, cmp);
@@ -823,7 +632,7 @@ TEST_F(BoundsCheckEliminationTest, ModArrayBoundsElimination) {
MakeArraySet(loop_body, new_array, bounds_check_i_mod_1, constant_10, DataType::Type::kInt32);
// array[i % 200] = 10;
- HRem* i_mod_200 = MakeBinOp<HRem>(loop_body, DataType::Type::kInt32, phi, constant_1);
+ HRem* i_mod_200 = MakeBinOp<HRem>(loop_body, DataType::Type::kInt32, phi, constant_200);
HBoundsCheck* bounds_check_i_mod_200 = MakeBoundsCheck(loop_body, i_mod_200, constant_10);
MakeArraySet(loop_body, new_array, bounds_check_i_mod_200, constant_10, DataType::Type::kInt32);
@@ -863,21 +672,13 @@ TEST_F(BoundsCheckEliminationTest, ModArrayBoundsElimination) {
constant_10,
DataType::Type::kInt32);
- // i++;
- HInstruction* add = MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, phi, constant_1);
- MakeGoto(loop_body);
-
- phi->ReplaceInput(add, 1u); // Update back-edge input.
-
//////////////////////////////////////////////////////////////////////////////////
- MakeExit(exit);
-
RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check_i_mod_10));
ASSERT_TRUE(IsRemoved(bounds_check_i_mod_1));
- ASSERT_TRUE(IsRemoved(bounds_check_i_mod_200));
+ ASSERT_FALSE(IsRemoved(bounds_check_i_mod_200));
ASSERT_TRUE(IsRemoved(bounds_check_i_mod_minus_10));
ASSERT_TRUE(IsRemoved(bounds_check_i_mod_array_len));
ASSERT_FALSE(IsRemoved(bounds_check_param_i_mod_10));
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index 2adf74ad64..872fa42a76 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -32,9 +32,6 @@ class InductionVarAnalysisTest : public OptimizingUnitTest {
public:
InductionVarAnalysisTest()
: iva_(nullptr),
- entry_(nullptr),
- return_(nullptr),
- exit_(nullptr),
parameter_(nullptr),
constant0_(nullptr),
constant1_(nullptr),
@@ -43,55 +40,27 @@ class InductionVarAnalysisTest : public OptimizingUnitTest {
constant100_(nullptr),
constantm1_(nullptr),
float_constant0_(nullptr) {
- graph_ = CreateGraph();
}
~InductionVarAnalysisTest() { }
- // Builds single for-loop at depth d.
- void BuildForLoop(int d, int n) {
- ASSERT_LT(d, n);
- loop_preheader_[d] = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(loop_preheader_[d]);
- loop_header_[d] = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(loop_header_[d]);
- loop_preheader_[d]->AddSuccessor(loop_header_[d]);
- if (d < (n - 1)) {
- BuildForLoop(d + 1, n);
- }
- loop_body_[d] = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(loop_body_[d]);
- loop_body_[d]->AddSuccessor(loop_header_[d]);
- if (d < (n - 1)) {
- loop_header_[d]->AddSuccessor(loop_preheader_[d + 1]);
- loop_header_[d + 1]->AddSuccessor(loop_body_[d]);
- } else {
- loop_header_[d]->AddSuccessor(loop_body_[d]);
- }
- }
-
// Builds a n-nested loop in CFG where each loop at depth 0 <= d < n
// is defined as "for (int i_d = 0; i_d < 100; i_d++)". Tests can further
// populate the loop with instructions to set up interesting scenarios.
- void BuildLoopNest(int n) {
+ void BuildLoopNest(size_t n) {
ASSERT_LE(n, 10);
+ HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
graph_->SetNumberOfVRegs(n + 3);
- // Build basic blocks with entry, nested loop, exit.
- entry_ = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry_);
- BuildForLoop(0, n);
- return_ = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(return_);
- exit_ = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(exit_);
- entry_->AddSuccessor(loop_preheader_[0]);
- loop_header_[0]->AddSuccessor(return_);
- return_->AddSuccessor(exit_);
- graph_->SetEntryBlock(entry_);
- graph_->SetExitBlock(exit_);
-
- // Provide entry and exit instructions.
+ // Build nested loops.
+ HBasicBlock* loop_pos = return_block;
+ for (size_t d = 0; d < n; ++d) {
+ std::tie(loop_preheader_[d], loop_header_[d], loop_body_[d]) = CreateWhileLoop(loop_pos);
+ loop_header_[d]->SwapSuccessors(); // Move the loop exit to the "else" successor.
+ loop_pos = loop_body_[d];
+ }
+
+ // Provide entry instructions.
parameter_ = MakeParam(DataType::Type::kReference);
constant0_ = graph_->GetIntConstant(0);
constant1_ = graph_->GetIntConstant(1);
@@ -100,32 +69,21 @@ class InductionVarAnalysisTest : public OptimizingUnitTest {
constant100_ = graph_->GetIntConstant(100);
constantm1_ = graph_->GetIntConstant(-1);
float_constant0_ = graph_->GetFloatConstant(0.0f);
- MakeReturnVoid(return_);
- MakeExit(exit_);
// Provide loop instructions.
for (int d = 0; d < n; d++) {
- MakeGoto(loop_preheader_[d]);
-
- basic_[d] = MakePhi(loop_header_[d], {constant0_, /* placeholder */ constant0_});
+ std::tie(basic_[d], increment_[d]) =
+ MakeLinearLoopVar(loop_header_[d], loop_body_[d], constant0_, constant1_);
HInstruction* compare = MakeCondition<HLessThan>(loop_header_[d], basic_[d], constant100_);
MakeIf(loop_header_[d], compare);
-
- increment_[d] = MakeBinOp<HAdd>(loop_body_[d], DataType::Type::kInt32, basic_[d], constant1_);
- MakeGoto(loop_body_[d]);
-
- basic_[d]->ReplaceInput(increment_[d], 1u); // Update back-edge input.
}
}
// Builds if-statement at depth d.
HPhi* BuildIf(int d, HBasicBlock** ifT, HBasicBlock** ifF) {
- HBasicBlock* cond = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* ifTrue = new (GetAllocator()) HBasicBlock(graph_);
- HBasicBlock* ifFalse = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(cond);
- graph_->AddBlock(ifTrue);
- graph_->AddBlock(ifFalse);
+ HBasicBlock* cond = AddNewBlock();
+ HBasicBlock* ifTrue = AddNewBlock();
+ HBasicBlock* ifFalse = AddNewBlock();
// Conditional split.
loop_header_[d]->ReplaceSuccessor(loop_body_[d], cond);
cond->AddSuccessor(ifTrue);
@@ -197,13 +155,9 @@ class InductionVarAnalysisTest : public OptimizingUnitTest {
}
// General building fields.
- HGraph* graph_;
HInductionVarAnalysis* iva_;
// Fixed basic blocks and instructions.
- HBasicBlock* entry_;
- HBasicBlock* return_;
- HBasicBlock* exit_;
HInstruction* parameter_; // "this"
HInstruction* constant0_;
HInstruction* constant1_;
@@ -236,7 +190,7 @@ TEST_F(InductionVarAnalysisTest, ProperLoopSetup) {
BuildLoopNest(10);
graph_->BuildDominatorTree();
- ASSERT_EQ(entry_->GetLoopInformation(), nullptr);
+ ASSERT_EQ(entry_block_->GetLoopInformation(), nullptr);
for (int d = 0; d < 1; d++) {
ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(),
(d == 0) ? nullptr
@@ -246,7 +200,7 @@ TEST_F(InductionVarAnalysisTest, ProperLoopSetup) {
ASSERT_EQ(loop_header_[d]->GetLoopInformation(),
loop_body_[d]->GetLoopInformation());
}
- ASSERT_EQ(exit_->GetLoopInformation(), nullptr);
+ ASSERT_EQ(exit_block_->GetLoopInformation(), nullptr);
}
TEST_F(InductionVarAnalysisTest, FindBasicInduction) {
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index bc970296ef..0c0b54eb23 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -33,10 +33,10 @@ using Value = InductionVarRange::Value;
class InductionVarRangeTest : public OptimizingUnitTest {
public:
InductionVarRangeTest()
- : graph_(CreateGraph()),
- iva_(new (GetAllocator()) HInductionVarAnalysis(graph_)),
+ : iva_(new (GetAllocator()) HInductionVarAnalysis(BuildGraph())),
range_(iva_) {
- BuildGraph();
+ // Set arbitrary range analysis hint while testing private methods.
+ SetHint(x_);
}
~InductionVarRangeTest() { }
@@ -58,54 +58,30 @@ class InductionVarRangeTest : public OptimizingUnitTest {
//
/** Constructs bare minimum graph. */
- void BuildGraph() {
+ HGraph* BuildGraph() {
+ return_block_ = InitEntryMainExitGraphWithReturnVoid();
graph_->SetNumberOfVRegs(1);
- entry_block_ = new (GetAllocator()) HBasicBlock(graph_);
- exit_block_ = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(entry_block_);
- graph_->AddBlock(exit_block_);
- graph_->SetEntryBlock(entry_block_);
- graph_->SetExitBlock(exit_block_);
// Two parameters.
x_ = MakeParam(DataType::Type::kInt32);
y_ = MakeParam(DataType::Type::kInt32);
- // Set arbitrary range analysis hint while testing private methods.
- SetHint(x_);
+ return graph_;
}
/** Constructs loop with given upper bound. */
void BuildLoop(int32_t lower, HInstruction* upper, int32_t stride) {
// Control flow.
- loop_preheader_ = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(loop_preheader_);
- loop_header_ = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(loop_header_);
- loop_body_ = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(loop_body_);
- HBasicBlock* return_block = new (GetAllocator()) HBasicBlock(graph_);
- graph_->AddBlock(return_block);
- entry_block_->AddSuccessor(loop_preheader_);
- loop_preheader_->AddSuccessor(loop_header_);
- loop_header_->AddSuccessor(loop_body_);
- loop_header_->AddSuccessor(return_block);
- loop_body_->AddSuccessor(loop_header_);
- return_block->AddSuccessor(exit_block_);
+ std::tie(loop_preheader_, loop_header_, loop_body_) = CreateWhileLoop(return_block_);
+ loop_header_->SwapSuccessors(); // Move the loop exit to the "else" successor.
// Instructions.
- MakeGoto(loop_preheader_);
HInstruction* lower_const = graph_->GetIntConstant(lower);
- HPhi* phi = MakePhi(loop_header_, {lower_const, /* placeholder */ lower_const}); // i = l
+ HPhi* phi;
+ std::tie(phi, increment_) = MakeLinearLoopVar(loop_header_, loop_body_, lower, stride);
if (stride > 0) {
condition_ = MakeCondition<HLessThan>(loop_header_, phi, upper); // i < u
} else {
condition_ = MakeCondition<HGreaterThan>(loop_header_, phi, upper); // i > u
}
MakeIf(loop_header_, condition_);
- increment_ = MakeBinOp<HAdd>(
- loop_body_, DataType::Type::kInt32, phi, graph_->GetIntConstant(stride)); // i += s
- phi->ReplaceInput(increment_, 1u); // Update back-edge input.
- MakeGoto(loop_body_);
- MakeReturnVoid(return_block);
- MakeExit(exit_block_);
}
/** Constructs SSA and performs induction variable analysis. */
@@ -339,9 +315,7 @@ class InductionVarRangeTest : public OptimizingUnitTest {
Value MaxValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, false); }
// General building fields.
- HGraph* graph_;
- HBasicBlock* entry_block_;
- HBasicBlock* exit_block_;
+ HBasicBlock* return_block_;
HBasicBlock* loop_preheader_;
HBasicBlock* loop_header_;
HBasicBlock* loop_body_;
diff --git a/compiler/optimizing/load_store_elimination_test.cc b/compiler/optimizing/load_store_elimination_test.cc
index 04f666ff49..ae6e1137c9 100644
--- a/compiler/optimizing/load_store_elimination_test.cc
+++ b/compiler/optimizing/load_store_elimination_test.cc
@@ -110,34 +110,21 @@ class LoadStoreEliminationTestBase : public SuperTest, public OptimizingUnitTest
// exit
void CreateTestControlFlowGraph() {
InitGraphAndParameters();
- pre_header_ = AddNewBlock();
- loop_ = AddNewBlock();
+ std::tie(pre_header_, loop_) = CreateDoWhileLoop(return_block_);
- 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_ = MakePhi(loop_, {c0, /* placeholder */ c0});
- MakeGoto(pre_header_);
+ std::tie(phi_, std::ignore) = MakeLinearLoopVar(loop_, loop_, /*initial=*/ 0, /*increment=*/ 1);
// loop block:
// suspend_check
// phi++;
// if (phi >= 128)
suspend_check_ = MakeSuspendCheck(loop_);
- HInstruction* inc_phi = MakeBinOp<HAdd>(loop_, DataType::Type::kInt32, phi_, c1);
HInstruction* cmp = MakeCondition<HGreaterThanOrEqual>(loop_, phi_, c128);
MakeIf(loop_, cmp);
- phi_->ReplaceInput(inc_phi, 1u); // Update back-edge input.
CreateEnvForSuspendCheck();
}
@@ -950,17 +937,9 @@ TEST_F(LoadStoreEliminationTest, VLoadDefaultValueAndVLoad) {
// o.foo = 3;
// return o.shadow$_klass_;
TEST_F(LoadStoreEliminationTest, DefaultShadowClass) {
- CreateGraph();
- AdjacencyListGraph blocks(
- graph_, GetAllocator(), "entry", "exit", {{"entry", "main"}, {"main", "exit"}});
-#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
- GET_BLOCK(entry);
- GET_BLOCK(main);
- GET_BLOCK(exit);
-#undef GET_BLOCK
+ HBasicBlock* main = InitEntryMainExitGraph();
- HInstruction* suspend_check = MakeSuspendCheck(entry);
- MakeGoto(entry);
+ HInstruction* suspend_check = MakeSuspendCheck(entry_block_);
ManuallyBuildEnvFor(suspend_check, {});
HInstruction* cls = MakeLoadClass(main);
@@ -975,9 +954,6 @@ TEST_F(LoadStoreEliminationTest, DefaultShadowClass) {
cls->CopyEnvironmentFrom(suspend_check->GetEnvironment());
new_inst->CopyEnvironmentFrom(suspend_check->GetEnvironment());
- MakeExit(exit);
-
- graph_->ClearDominanceInformation();
PerformLSE();
EXPECT_INS_REMOVED(new_inst);
@@ -996,17 +972,9 @@ TEST_F(LoadStoreEliminationTest, DefaultShadowClass) {
// o.foo = 3;
// return o.shadow$_monitor_;
TEST_F(LoadStoreEliminationTest, DefaultShadowMonitor) {
- CreateGraph();
- AdjacencyListGraph blocks(
- graph_, GetAllocator(), "entry", "exit", {{"entry", "main"}, {"main", "exit"}});
-#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
- GET_BLOCK(entry);
- GET_BLOCK(main);
- GET_BLOCK(exit);
-#undef GET_BLOCK
+ HBasicBlock* main = InitEntryMainExitGraph();
- HInstruction* suspend_check = MakeSuspendCheck(entry);
- MakeGoto(entry);
+ HInstruction* suspend_check = MakeSuspendCheck(entry_block_);
ManuallyBuildEnvFor(suspend_check, {});
HInstruction* cls = MakeLoadClass(main);
@@ -1021,9 +989,6 @@ TEST_F(LoadStoreEliminationTest, DefaultShadowMonitor) {
cls->CopyEnvironmentFrom(suspend_check->GetEnvironment());
new_inst->CopyEnvironmentFrom(suspend_check->GetEnvironment());
- MakeExit(exit);
-
- graph_->ClearDominanceInformation();
PerformLSE();
EXPECT_INS_REMOVED(new_inst);
@@ -1048,79 +1013,43 @@ TEST_F(LoadStoreEliminationTest, DefaultShadowMonitor) {
TEST_F(LoadStoreEliminationTest, ArrayLoopOverlap) {
ScopedObjectAccess soa(Thread::Current());
VariableSizedHandleScope vshs(soa.Self());
- CreateGraph(&vshs);
- AdjacencyListGraph blocks(graph_,
- GetAllocator(),
- "entry",
- "exit",
- { { "entry", "loop_pre_header" },
- { "loop_pre_header", "loop_entry" },
- { "loop_entry", "loop_body" },
- { "loop_entry", "loop_post" },
- { "loop_body", "loop_entry" },
- { "loop_post", "exit" } });
-#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
- GET_BLOCK(entry);
- GET_BLOCK(loop_pre_header);
- GET_BLOCK(loop_entry);
- GET_BLOCK(loop_body);
- GET_BLOCK(loop_post);
- GET_BLOCK(exit);
-#undef GET_BLOCK
+ HBasicBlock* ret = InitEntryMainExitGraph(&vshs);
+ auto [preheader, loop, body] = CreateWhileLoop(ret);
- HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
- HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
- HInstruction* eighty_const = graph_->GetConstant(DataType::Type::kInt32, 80);
- MakeGoto(entry);
+ HInstruction* zero_const = graph_->GetIntConstant(0);
+ HInstruction* one_const = graph_->GetIntConstant(1);
+ HInstruction* eighty_const = graph_->GetIntConstant(80);
- HInstruction* alloc_w = MakeNewArray(loop_pre_header, zero_const, eighty_const);
- MakeGoto(loop_pre_header);
- // environment
+ // preheader
+ HInstruction* alloc_w = MakeNewArray(preheader, zero_const, eighty_const);
ManuallyBuildEnvFor(alloc_w, {});
// loop-start
- HPhi* i_phi = MakePhi(loop_entry, {one_const, /* placeholder */ one_const});
- HPhi* t_phi = MakePhi(loop_entry, {zero_const, /* placeholder */ zero_const});
- HInstruction* suspend = MakeSuspendCheck(loop_entry);
- HInstruction* i_cmp_top = MakeCondition<HGreaterThanOrEqual>(loop_entry, i_phi, eighty_const);
- MakeIf(loop_entry, i_cmp_top);
- CHECK_EQ(loop_entry->GetSuccessors().size(), 2u);
- if (loop_entry->GetNormalSuccessors()[1] != loop_body) {
- loop_entry->SwapSuccessors();
- }
- CHECK_EQ(loop_entry->GetPredecessors().size(), 2u);
- if (loop_entry->GetPredecessors()[0] != loop_pre_header) {
- loop_entry->SwapPredecessors();
- }
+ auto [i_phi, i_add] = MakeLinearLoopVar(loop, body, one_const, one_const);
+ HPhi* t_phi = MakePhi(loop, {zero_const, /* placeholder */ zero_const});
+ HInstruction* suspend = MakeSuspendCheck(loop);
+ HInstruction* i_cmp_top = MakeCondition<HGreaterThanOrEqual>(loop, i_phi, eighty_const);
+ HIf* loop_if = MakeIf(loop, i_cmp_top);
+ CHECK(loop_if->IfTrueSuccessor() == ret);
// environment
ManuallyBuildEnvFor(suspend, { alloc_w, i_phi, t_phi });
// BODY
- HInstruction* last_i = MakeBinOp<HSub>(loop_body, DataType::Type::kInt32, i_phi, one_const);
- HInstruction* last_get = MakeArrayGet(loop_body, alloc_w, last_i, DataType::Type::kInt32);
- HInvoke* body_value =
- MakeInvokeStatic(loop_body, DataType::Type::kInt32, { last_get, one_const });
- HInstruction* body_set =
- MakeArraySet(loop_body, alloc_w, i_phi, body_value, DataType::Type::kInt32);
- HInstruction* body_get = MakeArrayGet(loop_body, alloc_w, i_phi, DataType::Type::kInt32);
- HInvoke* t_next = MakeInvokeStatic(loop_body, DataType::Type::kInt32, { body_get, t_phi });
- HInstruction* i_next = MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, i_phi, one_const);
- MakeGoto(loop_body);
+ HInstruction* last_i = MakeBinOp<HSub>(body, DataType::Type::kInt32, i_phi, one_const);
+ HInstruction* last_get = MakeArrayGet(body, alloc_w, last_i, DataType::Type::kInt32);
+ HInvoke* body_value = MakeInvokeStatic(body, DataType::Type::kInt32, { last_get, one_const });
+ HInstruction* body_set = MakeArraySet(body, alloc_w, i_phi, body_value, DataType::Type::kInt32);
+ HInstruction* body_get = MakeArrayGet(body, alloc_w, i_phi, DataType::Type::kInt32);
+ HInvoke* t_next = MakeInvokeStatic(body, DataType::Type::kInt32, { body_get, t_phi });
body_value->CopyEnvironmentFrom(suspend->GetEnvironment());
- i_phi->ReplaceInput(i_next, 1u); // Update back-edge input.
t_phi->ReplaceInput(t_next, 1u); // Update back-edge input.
t_next->CopyEnvironmentFrom(suspend->GetEnvironment());
- // loop-post
- MakeReturn(loop_post, t_phi);
-
- // exit
- MakeExit(exit);
+ // ret
+ MakeReturn(ret, t_phi);
- graph_->ClearDominanceInformation();
- graph_->ClearLoopInformation();
PerformLSE();
// TODO Technically this is optimizable. LSE just needs to add phis to keep
@@ -1157,90 +1086,54 @@ TEST_F(LoadStoreEliminationTest, ArrayLoopOverlap) {
TEST_F(LoadStoreEliminationTest, ArrayLoopOverlap2) {
ScopedObjectAccess soa(Thread::Current());
VariableSizedHandleScope vshs(soa.Self());
- CreateGraph(&vshs);
- AdjacencyListGraph blocks(graph_,
- GetAllocator(),
- "entry",
- "exit",
- { { "entry", "loop_pre_header" },
- { "loop_pre_header", "loop_entry" },
- { "loop_entry", "loop_body" },
- { "loop_entry", "loop_post" },
- { "loop_body", "loop_entry" },
- { "loop_post", "exit" } });
-#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
- GET_BLOCK(entry);
- GET_BLOCK(loop_pre_header);
- GET_BLOCK(loop_entry);
- GET_BLOCK(loop_body);
- GET_BLOCK(loop_post);
- GET_BLOCK(exit);
-#undef GET_BLOCK
+ HBasicBlock* ret = InitEntryMainExitGraph(&vshs);
+ auto [preheader, loop, body] = CreateWhileLoop(ret);
- HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
- HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
- HInstruction* eighty_const = graph_->GetConstant(DataType::Type::kInt32, 80);
- MakeGoto(entry);
+ HInstruction* zero_const = graph_->GetIntConstant(0);
+ HInstruction* one_const = graph_->GetIntConstant(1);
+ HInstruction* eighty_const = graph_->GetIntConstant(80);
- HInstruction* alloc_w = MakeNewArray(loop_pre_header, zero_const, eighty_const);
- MakeGoto(loop_pre_header);
+ // preheader
+ HInstruction* alloc_w = MakeNewArray(preheader, zero_const, eighty_const);
// environment
ManuallyBuildEnvFor(alloc_w, {});
// loop-start
- HPhi* i_phi = MakePhi(loop_entry, {one_const, /* placeholder */ one_const});
- HPhi* t_phi = MakePhi(loop_entry, {zero_const, /* placeholder */ zero_const});
- HInstruction* suspend = MakeSuspendCheck(loop_entry);
- HInstruction* i_cmp_top = MakeCondition<HGreaterThanOrEqual>(loop_entry, i_phi, eighty_const);
- MakeIf(loop_entry, i_cmp_top);
- CHECK_EQ(loop_entry->GetSuccessors().size(), 2u);
- if (loop_entry->GetNormalSuccessors()[1] != loop_body) {
- loop_entry->SwapSuccessors();
- }
- CHECK_EQ(loop_entry->GetPredecessors().size(), 2u);
- if (loop_entry->GetPredecessors()[0] != loop_pre_header) {
- loop_entry->SwapPredecessors();
- }
+ auto [i_phi, i_add] = MakeLinearLoopVar(loop, body, one_const, one_const);
+ HPhi* t_phi = MakePhi(loop, {zero_const, /* placeholder */ zero_const});
+ HInstruction* suspend = MakeSuspendCheck(loop);
+ HInstruction* i_cmp_top = MakeCondition<HGreaterThanOrEqual>(loop, i_phi, eighty_const);
+ HIf* loop_if = MakeIf(loop, i_cmp_top);
+ CHECK(loop_if->IfTrueSuccessor() == ret);
// environment
ManuallyBuildEnvFor(suspend, { alloc_w, i_phi, t_phi });
// BODY
- HInstruction* last_i = MakeBinOp<HSub>(loop_body, DataType::Type::kInt32, i_phi, one_const);
+ HInstruction* last_i = MakeBinOp<HSub>(body, DataType::Type::kInt32, i_phi, one_const);
auto make_instructions = [&](HInstruction* last_t_value) {
- HInstruction* last_get = MakeArrayGet(loop_body, alloc_w, last_i, DataType::Type::kInt32);
- HInvoke* body_value =
- MakeInvokeStatic(loop_body, DataType::Type::kInt32, { last_get, one_const });
- HInstruction* body_set =
- MakeArraySet(loop_body, alloc_w, i_phi, body_value, DataType::Type::kInt32);
- HInstruction* body_get = MakeArrayGet(loop_body, alloc_w, i_phi, DataType::Type::kInt32);
- HInvoke* t_next =
- MakeInvokeStatic(loop_body, DataType::Type::kInt32, { body_get, last_t_value });
+ HInstruction* last_get = MakeArrayGet(body, alloc_w, last_i, DataType::Type::kInt32);
+ HInvoke* body_value = MakeInvokeStatic(body, DataType::Type::kInt32, { last_get, one_const });
+ HInstruction* body_set = MakeArraySet(body, alloc_w, i_phi, body_value, DataType::Type::kInt32);
+ HInstruction* body_get = MakeArrayGet(body, alloc_w, i_phi, DataType::Type::kInt32);
+ HInvoke* t_next = MakeInvokeStatic(body, DataType::Type::kInt32, { body_get, last_t_value });
return std::make_tuple(last_get, body_value, body_set, body_get, t_next);
};
auto [last_get_1, body_value_1, body_set_1, body_get_1, t_next_1] = make_instructions(t_phi);
auto [last_get_2, body_value_2, body_set_2, body_get_2, t_next_2] = make_instructions(t_next_1);
auto [last_get_3, body_value_3, body_set_3, body_get_3, t_next_3] = make_instructions(t_next_2);
- HInstruction* i_next = MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, i_phi, one_const);
- MakeGoto(loop_body);
body_value_1->CopyEnvironmentFrom(suspend->GetEnvironment());
body_value_2->CopyEnvironmentFrom(suspend->GetEnvironment());
body_value_3->CopyEnvironmentFrom(suspend->GetEnvironment());
- i_phi->ReplaceInput(i_next, 1u); // Update back-edge input.
t_phi->ReplaceInput(t_next_3, 1u); // Update back-edge input.
t_next_1->CopyEnvironmentFrom(suspend->GetEnvironment());
t_next_2->CopyEnvironmentFrom(suspend->GetEnvironment());
t_next_3->CopyEnvironmentFrom(suspend->GetEnvironment());
- // loop-post
- MakeReturn(loop_post, t_phi);
-
- // exit
- MakeExit(exit);
+ // ret
+ MakeReturn(ret, t_phi);
- graph_->ClearDominanceInformation();
- graph_->ClearLoopInformation();
PerformLSE();
// TODO Technically this is optimizable. LSE just needs to add phis to keep
@@ -1271,36 +1164,17 @@ TEST_F(LoadStoreEliminationTest, ArrayLoopOverlap2) {
TEST_F(LoadStoreEliminationTest, ArrayNonLoopPhi) {
ScopedObjectAccess soa(Thread::Current());
VariableSizedHandleScope vshs(soa.Self());
- CreateGraph(&vshs);
- AdjacencyListGraph blocks(graph_,
- GetAllocator(),
- "entry",
- "exit",
- { { "entry", "start" },
- { "start", "left" },
- { "start", "right" },
- { "left", "ret" },
- { "right", "ret" },
- { "ret", "exit" } });
-#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
- GET_BLOCK(entry);
- GET_BLOCK(start);
- GET_BLOCK(left);
- GET_BLOCK(right);
- GET_BLOCK(ret);
- GET_BLOCK(exit);
-#undef GET_BLOCK
+ HBasicBlock* ret = InitEntryMainExitGraph(&vshs);
- HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
- HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
- HInstruction* two_const = graph_->GetConstant(DataType::Type::kInt32, 2);
HInstruction* param = MakeParam(DataType::Type::kBool);
+ HInstruction* zero_const = graph_->GetIntConstant(0);
+ HInstruction* one_const = graph_->GetIntConstant(1);
+ HInstruction* two_const = graph_->GetIntConstant(2);
- MakeGoto(entry);
+ auto [start, left, right] = CreateDiamondPattern(ret, param);
+ // start
HInstruction* alloc_w = MakeNewArray(start, zero_const, two_const);
- MakeIf(start, param);
- // environment
ManuallyBuildEnvFor(alloc_w, {});
// left
@@ -1309,7 +1183,6 @@ TEST_F(LoadStoreEliminationTest, ArrayNonLoopPhi) {
MakeArraySet(left, alloc_w, zero_const, left_value, DataType::Type::kInt32);
HInstruction* left_set_2 =
MakeArraySet(left, alloc_w, one_const, zero_const, DataType::Type::kInt32);
- MakeGoto(left);
ManuallyBuildEnvFor(left_value, { alloc_w });
// right
@@ -1318,7 +1191,6 @@ TEST_F(LoadStoreEliminationTest, ArrayNonLoopPhi) {
MakeArraySet(right, alloc_w, zero_const, right_value, DataType::Type::kInt32);
HInstruction* right_set_2 =
MakeArraySet(right, alloc_w, one_const, zero_const, DataType::Type::kInt32);
- MakeGoto(right);
ManuallyBuildEnvFor(right_value, { alloc_w });
// ret
@@ -1327,11 +1199,6 @@ TEST_F(LoadStoreEliminationTest, ArrayNonLoopPhi) {
HInstruction* add = MakeBinOp<HAdd>(ret, DataType::Type::kInt32, read_1, read_2);
MakeReturn(ret, add);
- // exit
- MakeExit(exit);
-
- graph_->ClearDominanceInformation();
- graph_->ClearLoopInformation();
PerformLSE();
EXPECT_INS_REMOVED(read_1);
@@ -1349,35 +1216,17 @@ TEST_F(LoadStoreEliminationTest, ArrayNonLoopPhi) {
TEST_F(LoadStoreEliminationTest, ArrayMergeDefault) {
ScopedObjectAccess soa(Thread::Current());
VariableSizedHandleScope vshs(soa.Self());
- CreateGraph(&vshs);
- AdjacencyListGraph blocks(graph_,
- GetAllocator(),
- "entry",
- "exit",
- { { "entry", "start" },
- { "start", "left" },
- { "start", "right" },
- { "left", "ret" },
- { "right", "ret" },
- { "ret", "exit" } });
-#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
- GET_BLOCK(entry);
- GET_BLOCK(start);
- GET_BLOCK(left);
- GET_BLOCK(right);
- GET_BLOCK(ret);
- GET_BLOCK(exit);
-#undef GET_BLOCK
+ HBasicBlock* ret = InitEntryMainExitGraph(&vshs);
- HInstruction* zero_const = graph_->GetConstant(DataType::Type::kInt32, 0);
- HInstruction* one_const = graph_->GetConstant(DataType::Type::kInt32, 1);
- HInstruction* two_const = graph_->GetConstant(DataType::Type::kInt32, 2);
HInstruction* param = MakeParam(DataType::Type::kBool);
- MakeGoto(entry);
+ HInstruction* zero_const = graph_->GetIntConstant(0);
+ HInstruction* one_const = graph_->GetIntConstant(1);
+ HInstruction* two_const = graph_->GetIntConstant(2);
+ auto [start, left, right] = CreateDiamondPattern(ret, param);
+
+ // start
HInstruction* alloc_w = MakeNewArray(start, zero_const, two_const);
- MakeIf(start, param);
- // environment
ArenaVector<HInstruction*> alloc_locals({}, GetAllocator()->Adapter(kArenaAllocInstruction));
ManuallyBuildEnvFor(alloc_w, {});
@@ -1386,14 +1235,12 @@ TEST_F(LoadStoreEliminationTest, ArrayMergeDefault) {
MakeArraySet(left, alloc_w, zero_const, one_const, DataType::Type::kInt32);
HInstruction* left_set_2 =
MakeArraySet(left, alloc_w, zero_const, zero_const, DataType::Type::kInt32);
- MakeGoto(left);
// right
HInstruction* right_set_1 =
MakeArraySet(right, alloc_w, one_const, one_const, DataType::Type::kInt32);
HInstruction* right_set_2 =
MakeArraySet(right, alloc_w, one_const, zero_const, DataType::Type::kInt32);
- MakeGoto(right);
// ret
HInstruction* read_1 = MakeArrayGet(ret, alloc_w, zero_const, DataType::Type::kInt32);
@@ -1401,11 +1248,6 @@ TEST_F(LoadStoreEliminationTest, ArrayMergeDefault) {
HInstruction* add = MakeBinOp<HAdd>(ret, DataType::Type::kInt32, read_1, read_2);
MakeReturn(ret, add);
- // exit
- MakeExit(exit);
-
- graph_->ClearDominanceInformation();
- graph_->ClearLoopInformation();
PerformLSE();
EXPECT_INS_REMOVED(read_1);
@@ -1425,40 +1267,22 @@ TEST_F(LoadStoreEliminationTest, ArrayMergeDefault) {
TEST_F(LoadStoreEliminationTest, ArrayLoopAliasing1) {
ScopedObjectAccess soa(Thread::Current());
VariableSizedHandleScope vshs(soa.Self());
- CreateGraph(&vshs);
- AdjacencyListGraph blocks(graph_,
- GetAllocator(),
- "entry",
- "exit",
- { { "entry", "preheader" },
- { "preheader", "loop" },
- { "loop", "body" },
- { "body", "loop" },
- { "loop", "ret" },
- { "ret", "exit" } });
-#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
- GET_BLOCK(entry);
- GET_BLOCK(preheader);
- GET_BLOCK(loop);
- GET_BLOCK(body);
- GET_BLOCK(ret);
- GET_BLOCK(exit);
-#undef GET_BLOCK
+ HBasicBlock* ret = InitEntryMainExitGraph(&vshs);
+ auto [preheader, loop, body] = CreateWhileLoop(ret);
+ loop->SwapSuccessors(); // Move the loop exit to the "else" successor.
+
HInstruction* n = MakeParam(DataType::Type::kInt32);
HInstruction* c0 = graph_->GetIntConstant(0);
HInstruction* c1 = graph_->GetIntConstant(1);
- // entry
- HInstruction* cls = MakeLoadClass(entry);
- HInstruction* array = MakeNewArray(entry, cls, n);
- MakeGoto(entry);
+ // preheader
+ HInstruction* cls = MakeLoadClass(preheader);
+ HInstruction* array = MakeNewArray(preheader, cls, n);
ManuallyBuildEnvFor(cls, {});
ManuallyBuildEnvFor(array, {});
- MakeGoto(preheader);
-
// loop
- HPhi* i_phi = MakePhi(loop, {c0, /*placeholder*/ c0});
+ auto [i_phi, i_add] = MakeLinearLoopVar(loop, body, c0, c1);
HInstruction* loop_suspend_check = MakeSuspendCheck(loop);
HInstruction* loop_cond = MakeCondition<HLessThan>(loop, i_phi, n);
HIf* loop_if = MakeIf(loop, loop_cond);
@@ -1466,24 +1290,13 @@ TEST_F(LoadStoreEliminationTest, ArrayLoopAliasing1) {
ManuallyBuildEnvFor(loop_suspend_check, {});
// body
- HInstruction* body_set =
- MakeArraySet(body, array, i_phi, i_phi, DataType::Type::kInt32, /*dex_pc=*/ 0u);
- HInstruction* body_add = MakeBinOp<HAdd>(body, DataType::Type::kInt32, i_phi, c1);
- MakeGoto(body);
-
- // Update `i_phi`'s back-edge input.
- i_phi->ReplaceInput(body_add, 1u);
+ HInstruction* body_set = MakeArraySet(body, array, i_phi, i_phi, DataType::Type::kInt32);
// ret
HInstruction* ret_sub = MakeBinOp<HSub>(ret, DataType::Type::kInt32, i_phi, c1);
HInstruction* ret_get = MakeArrayGet(ret, array, ret_sub, DataType::Type::kInt32);
MakeReturn(ret, ret_get);
- // exit
- MakeExit(exit);
-
- graph_->ClearDominanceInformation();
- graph_->ClearLoopInformation();
PerformLSE();
EXPECT_INS_RETAINED(cls);
@@ -1502,40 +1315,22 @@ TEST_F(LoadStoreEliminationTest, ArrayLoopAliasing1) {
TEST_F(LoadStoreEliminationTest, ArrayLoopAliasing2) {
ScopedObjectAccess soa(Thread::Current());
VariableSizedHandleScope vshs(soa.Self());
- CreateGraph(&vshs);
- AdjacencyListGraph blocks(graph_,
- GetAllocator(),
- "entry",
- "exit",
- { { "entry", "preheader" },
- { "preheader", "loop" },
- { "loop", "body" },
- { "body", "loop" },
- { "loop", "ret" },
- { "ret", "exit" } });
-#define GET_BLOCK(name) HBasicBlock* name = blocks.Get(#name)
- GET_BLOCK(entry);
- GET_BLOCK(preheader);
- GET_BLOCK(loop);
- GET_BLOCK(body);
- GET_BLOCK(ret);
- GET_BLOCK(exit);
-#undef GET_BLOCK
+ HBasicBlock* ret = InitEntryMainExitGraph(&vshs);
+ auto [preheader, loop, body] = CreateWhileLoop(ret);
+ loop->SwapSuccessors(); // Move the loop exit to the "else" successor.
+
HInstruction* n = MakeParam(DataType::Type::kInt32);
HInstruction* c0 = graph_->GetIntConstant(0);
HInstruction* c1 = graph_->GetIntConstant(1);
- // entry
- HInstruction* cls = MakeLoadClass(entry);
- HInstruction* array = MakeNewArray(entry, cls, n);
- MakeGoto(entry);
+ // preheader
+ HInstruction* cls = MakeLoadClass(preheader);
+ HInstruction* array = MakeNewArray(preheader, cls, n);
ManuallyBuildEnvFor(cls, {});
ManuallyBuildEnvFor(array, {});
- MakeGoto(preheader);
-
// loop
- HPhi* i_phi = MakePhi(loop, {c0, /* placeholder */ c0});
+ auto [i_phi, i_add] = MakeLinearLoopVar(loop, body, c0, c1);
HInstruction* loop_suspend_check = MakeSuspendCheck(loop);
HInstruction* loop_cond = MakeCondition<HLessThan>(loop, i_phi, n);
HIf* loop_if = MakeIf(loop, loop_cond);
@@ -1544,11 +1339,6 @@ TEST_F(LoadStoreEliminationTest, ArrayLoopAliasing2) {
// body
HInstruction* body_set = MakeArraySet(body, array, i_phi, i_phi, DataType::Type::kInt32);
- HInstruction* body_add = MakeBinOp<HAdd>(body, DataType::Type::kInt32, i_phi, c1);
- MakeGoto(body);
-
- // Update `i_phi`'s back-edge input.
- i_phi->ReplaceInput(body_add, 1u);
// ret
HInstruction* ret_sub = MakeBinOp<HSub>(ret, DataType::Type::kInt32, i_phi, c1);
@@ -1557,11 +1347,6 @@ TEST_F(LoadStoreEliminationTest, ArrayLoopAliasing2) {
HInstruction* ret_add = MakeBinOp<HAdd>(ret, DataType::Type::kInt32, ret_get1, ret_get2);
MakeReturn(ret, ret_add);
- // exit
- MakeExit(exit);
-
- graph_->ClearDominanceInformation();
- graph_->ClearLoopInformation();
PerformLSE();
EXPECT_INS_RETAINED(cls);
@@ -1721,41 +1506,30 @@ TEST_F(LoadStoreEliminationTest, PartialUnknownMerge) {
TEST_F(LoadStoreEliminationTest, PartialLoadPreserved) {
ScopedObjectAccess soa(Thread::Current());
VariableSizedHandleScope vshs(soa.Self());
- CreateGraph(&vshs);
- AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
- "exit_REAL",
- { { "entry", "left" },
- { "entry", "right" },
- { "left", "exit" },
- { "right", "exit" },
- { "exit", "exit_REAL" } }));
- HBasicBlock* entry = blks.Get("entry");
- HBasicBlock* left = blks.Get("left");
- HBasicBlock* right = blks.Get("right");
- HBasicBlock* exit = blks.Get("exit");
+ HBasicBlock* ret = InitEntryMainExitGraph(&vshs);
+
HInstruction* bool_value = MakeParam(DataType::Type::kBool);
HInstruction* c1 = graph_->GetIntConstant(1);
HInstruction* c2 = graph_->GetIntConstant(2);
- HInstruction* cls = MakeLoadClass(entry);
- HInstruction* new_inst = MakeNewInstance(entry, cls);
- MakeIf(entry, bool_value);
+ auto [start, left, right] = CreateDiamondPattern(ret, bool_value);
+
+ HInstruction* cls = MakeLoadClass(start);
+ HInstruction* new_inst = MakeNewInstance(start, cls);
ManuallyBuildEnvFor(cls, {});
new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
HInstruction* write_left = MakeIFieldSet(left, new_inst, c1, MemberOffset(32));
HInstruction* call_left = MakeInvokeStatic(left, DataType::Type::kVoid, { new_inst });
- MakeGoto(left);
call_left->CopyEnvironmentFrom(cls->GetEnvironment());
HInstruction* write_right = MakeIFieldSet(right, new_inst, c2, MemberOffset(32));
- MakeGoto(right);
HInstruction* read_bottom =
- MakeIFieldGet(exit, new_inst, DataType::Type::kInt32, MemberOffset(32));
- MakeReturn(exit, read_bottom);
+ MakeIFieldGet(ret, new_inst, DataType::Type::kInt32, MemberOffset(32));
+ MakeReturn(ret, read_bottom);
- PerformLSE(blks);
+ PerformLSE();
EXPECT_INS_RETAINED(read_bottom) << *read_bottom;
EXPECT_INS_RETAINED(write_right) << *write_right;
@@ -1783,57 +1557,35 @@ TEST_F(LoadStoreEliminationTest, PartialLoadPreserved) {
TEST_F(LoadStoreEliminationTest, PartialLoadPreserved2) {
ScopedObjectAccess soa(Thread::Current());
VariableSizedHandleScope vshs(soa.Self());
- CreateGraph(&vshs);
- AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
- "exit_REAL",
- { { "entry", "left" },
- { "entry", "right_start" },
- { "left", "exit" },
- { "right_start", "right_first" },
- { "right_start", "right_second" },
- { "right_first", "right_end" },
- { "right_second", "right_end" },
- { "right_end", "exit" },
- { "exit", "exit_REAL" } }));
- HBasicBlock* entry = blks.Get("entry");
- HBasicBlock* left = blks.Get("left");
- HBasicBlock* right_start = blks.Get("right_start");
- HBasicBlock* right_first = blks.Get("right_first");
- HBasicBlock* right_second = blks.Get("right_second");
- HBasicBlock* right_end = blks.Get("right_end");
- HBasicBlock* exit = blks.Get("exit");
+ HBasicBlock* ret = InitEntryMainExitGraph(&vshs);
+
HInstruction* bool_value = MakeParam(DataType::Type::kBool);
HInstruction* bool_value_2 = MakeParam(DataType::Type::kBool);
HInstruction* c1 = graph_->GetIntConstant(1);
HInstruction* c2 = graph_->GetIntConstant(2);
HInstruction* c3 = graph_->GetIntConstant(3);
- HInstruction* cls = MakeLoadClass(entry);
- HInstruction* new_inst = MakeNewInstance(entry, cls);
- MakeIf(entry, bool_value);
+ auto [start, left, right_end] = CreateDiamondPattern(ret, bool_value);
+ auto [right_start, right_first, right_second] = CreateDiamondPattern(right_end, bool_value_2);
+
+ HInstruction* cls = MakeLoadClass(start);
+ HInstruction* new_inst = MakeNewInstance(start, cls);
ManuallyBuildEnvFor(cls, {});
new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
HInstruction* write_left = MakeIFieldSet(left, new_inst, c1, MemberOffset(32));
HInstruction* call_left = MakeInvokeStatic(left, DataType::Type::kVoid, { new_inst });
- MakeGoto(left);
call_left->CopyEnvironmentFrom(cls->GetEnvironment());
- MakeIf(right_start, bool_value_2);
-
HInstruction* write_right_first = MakeIFieldSet(right_first, new_inst, c2, MemberOffset(32));
- MakeGoto(right_first);
HInstruction* write_right_second = MakeIFieldSet(right_second, new_inst, c3, MemberOffset(32));
- MakeGoto(right_second);
-
- MakeGoto(right_end);
HInstruction* read_bottom =
- MakeIFieldGet(exit, new_inst, DataType::Type::kInt32, MemberOffset(32));
- MakeReturn(exit, read_bottom);
+ MakeIFieldGet(ret, new_inst, DataType::Type::kInt32, MemberOffset(32));
+ MakeReturn(ret, read_bottom);
- PerformLSE(blks);
+ PerformLSE();
EXPECT_INS_RETAINED(read_bottom);
EXPECT_INS_RETAINED(write_right_first);
@@ -2047,50 +1799,35 @@ TEST_F(LoadStoreEliminationTest, DISABLED_PartialLoadPreserved4) {
TEST_F(LoadStoreEliminationTest, PartialLoadPreserved5) {
ScopedObjectAccess soa(Thread::Current());
VariableSizedHandleScope vshs(soa.Self());
- CreateGraph(&vshs);
- AdjacencyListGraph blks(SetupFromAdjacencyList("entry",
- "exit",
- {{"entry", "left"},
- {"entry", "right"},
- {"left", "breturn"},
- {"right", "breturn"},
- {"breturn", "exit"}}));
-#define GET_BLOCK(name) HBasicBlock* name = blks.Get(#name)
- GET_BLOCK(entry);
- GET_BLOCK(exit);
- GET_BLOCK(breturn);
- GET_BLOCK(left);
- GET_BLOCK(right);
-#undef GET_BLOCK
+ HBasicBlock* breturn = InitEntryMainExitGraph(&vshs);
+
HInstruction* bool_value = MakeParam(DataType::Type::kBool);
HInstruction* c1 = graph_->GetIntConstant(1);
HInstruction* c2 = graph_->GetIntConstant(2);
- HInstruction* cls = MakeLoadClass(entry);
- HInstruction* new_inst = MakeNewInstance(entry, cls);
- MakeIf(entry, bool_value);
+ auto [start, left, right] = CreateDiamondPattern(breturn, bool_value);
+
+ // start
+ HInstruction* cls = MakeLoadClass(start);
+ HInstruction* new_inst = MakeNewInstance(start, cls);
ManuallyBuildEnvFor(cls, {});
new_inst->CopyEnvironmentFrom(cls->GetEnvironment());
HInstruction* call_left = MakeInvokeStatic(left, DataType::Type::kVoid, { new_inst });
HInstruction* write_left = MakeIFieldSet(left, new_inst, c1, MemberOffset(32));
HInstruction* call2_left = MakeInvokeStatic(left, DataType::Type::kVoid, {});
- MakeGoto(left);
call_left->CopyEnvironmentFrom(cls->GetEnvironment());
call2_left->CopyEnvironmentFrom(cls->GetEnvironment());
HInstruction* write_right = MakeIFieldSet(right, new_inst, c2, MemberOffset(32));
HInstruction* call_right = MakeInvokeStatic(right, DataType::Type::kVoid, {});
- MakeGoto(right);
call_right->CopyEnvironmentFrom(cls->GetEnvironment());
HInstruction* read_bottom =
MakeIFieldGet(breturn, new_inst, DataType::Type::kInt32, MemberOffset(32));
MakeReturn(breturn, read_bottom);
- MakeExit(exit);
-
- PerformLSE(blks);
+ PerformLSE();
EXPECT_INS_RETAINED(read_bottom);
EXPECT_INS_RETAINED(write_right);
diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h
index f0a279ca4d..f6267c5867 100644
--- a/compiler/optimizing/optimizing_unit_test.h
+++ b/compiler/optimizing/optimizing_unit_test.h
@@ -342,6 +342,53 @@ class OptimizingUnitTestHelper {
return {if_block, then_block, else_block};
}
+ // Insert "pre-header", "loop-header" and "loop-body" blocks before a given `loop_exit` block
+ // and connect them in a `while (...) { ... }` loop pattern. Return the new blocks.
+ // Adds `HGoto` to the "pre-header" and "loop-body" blocks but leaves the "loop-header" block
+ // empty, leaving the construction of an appropriate condition and `HIf` to the caller.
+ // Note: The `loop_exit` shall be the "then" successor of the "loop-header". If the `loop_exit`
+ // is needed as the "else" successor, use `HBlock::SwapSuccessors()` to adjust the order.
+ std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateWhileLoop(HBasicBlock* loop_exit) {
+ HBasicBlock* pre_header = AddNewBlock();
+ HBasicBlock* loop_header = AddNewBlock();
+ HBasicBlock* loop_body = AddNewBlock();
+
+ HBasicBlock* predecessor = loop_exit->GetSinglePredecessor();
+ predecessor->ReplaceSuccessor(loop_exit, pre_header);
+
+ pre_header->AddSuccessor(loop_header);
+ loop_header->AddSuccessor(loop_exit); // true successor
+ loop_header->AddSuccessor(loop_body); // false successor
+ loop_body->AddSuccessor(loop_header);
+
+ MakeGoto(pre_header);
+ MakeGoto(loop_body);
+
+ return {pre_header, loop_header, loop_body};
+ }
+
+ // Insert "pre-header" and "loop" blocks before a given `loop_exit` block and connect them in a
+ // `do { ... } while (...);` loop pattern. Return the new blocks. Adds `HGoto` to the "pre-header"
+ // block but leaves the "loop" block empty, leaving the construction of an appropriate condition
+ // and `HIf` to the caller.
+ // Note: The `loop_exit` shall be the "then" successor of the "loop". If the `loop_exit`
+ // is needed as the "else" successor, use `HBlock::SwapSuccessors()` to adjust the order.
+ std::tuple<HBasicBlock*, HBasicBlock*> CreateDoWhileLoop(HBasicBlock* loop_exit) {
+ HBasicBlock* pre_header = AddNewBlock();
+ HBasicBlock* loop = AddNewBlock();
+
+ HBasicBlock* predecessor = loop_exit->GetSinglePredecessor();
+ predecessor->ReplaceSuccessor(loop_exit, pre_header);
+
+ pre_header->AddSuccessor(loop);
+ loop->AddSuccessor(loop_exit); // true successor
+ loop->AddSuccessor(loop); // fakse successor
+
+ MakeGoto(pre_header);
+
+ return {pre_header, loop};
+ }
+
HBasicBlock* AddNewBlock() {
HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
graph_->AddBlock(block);
@@ -671,8 +718,8 @@ class OptimizingUnitTestHelper {
HPhi* MakePhi(HBasicBlock* block, const std::vector<HInstruction*>& ins) {
EXPECT_GE(ins.size(), 2u) << "Phi requires at least 2 inputs";
- HPhi* phi =
- new (GetAllocator()) HPhi(GetAllocator(), kNoRegNumber, ins.size(), ins[0]->GetType());
+ DataType::Type type = DataType::Kind(ins[0]->GetType());
+ HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), kNoRegNumber, ins.size(), type);
for (auto [i, idx] : ZipCount(MakeIterationRange(ins))) {
phi->SetRawInputAt(idx, i);
}
@@ -680,6 +727,25 @@ class OptimizingUnitTestHelper {
return phi;
}
+ std::tuple<HPhi*, HAdd*> MakeLinearLoopVar(HBasicBlock* header,
+ HBasicBlock* body,
+ int32_t initial,
+ int32_t increment) {
+ HInstruction* initial_const = graph_->GetIntConstant(initial);
+ HInstruction* increment_const = graph_->GetIntConstant(increment);
+ return MakeLinearLoopVar(header, body, initial_const, increment_const);
+ }
+
+ std::tuple<HPhi*, HAdd*> MakeLinearLoopVar(HBasicBlock* header,
+ HBasicBlock* body,
+ HInstruction* initial,
+ HInstruction* increment) {
+ HPhi* phi = MakePhi(header, {initial, /* placeholder */ initial});
+ HAdd* add = MakeBinOp<HAdd>(body, phi->GetType(), phi, increment);
+ phi->ReplaceInput(add, 1u); // Update back-edge input.
+ return {phi, add};
+ }
+
dex::TypeIndex DefaultTypeIndexForType(DataType::Type type) {
switch (type) {
case DataType::Type::kBool:
diff --git a/compiler/optimizing/superblock_cloner_test.cc b/compiler/optimizing/superblock_cloner_test.cc
index 8cef156e70..11d7db8b7e 100644
--- a/compiler/optimizing/superblock_cloner_test.cc
+++ b/compiler/optimizing/superblock_cloner_test.cc
@@ -39,26 +39,6 @@ class SuperblockClonerTest : public OptimizingUnitTest {
return return_block;
}
- void CreateBasicLoopControlFlow(HBasicBlock* position,
- HBasicBlock* successor,
- /* out */ HBasicBlock** header_p,
- /* out */ HBasicBlock** body_p) {
- HBasicBlock* loop_preheader = AddNewBlock();
- HBasicBlock* loop_header = AddNewBlock();
- HBasicBlock* loop_body = AddNewBlock();
-
- position->ReplaceSuccessor(successor, loop_preheader);
-
- loop_preheader->AddSuccessor(loop_header);
- // Loop exit first to have a proper exit condition/target for HIf.
- loop_header->AddSuccessor(successor);
- loop_header->AddSuccessor(loop_body);
- loop_body->AddSuccessor(loop_header);
-
- *header_p = loop_header;
- *body_p = loop_body;
- }
-
void CreateBasicLoopDataFlow(HBasicBlock* loop_header, HBasicBlock* loop_body) {
uint32_t dex_pc = 0;
@@ -83,7 +63,6 @@ class SuperblockClonerTest : public OptimizingUnitTest {
HInstruction* array_set =
MakeArraySet(loop_body, null_check, bounds_check, add, DataType::Type::kInt32, dex_pc);
HInstruction* induction_inc = MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, phi, const_1);
- MakeGoto(loop_body);
phi->ReplaceInput(induction_inc, 1u); // Update back-edge input.
@@ -102,11 +81,8 @@ class SuperblockClonerTest : public OptimizingUnitTest {
};
TEST_F(SuperblockClonerTest, IndividualInstrCloner) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
-
HBasicBlock* return_block = InitGraphAndParameters();
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
+ auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
CreateBasicLoopDataFlow(header, loop_body);
graph_->BuildDominatorTree();
EXPECT_TRUE(CheckGraph());
@@ -117,12 +93,12 @@ TEST_F(SuperblockClonerTest, IndividualInstrCloner) {
visitor.VisitInsertionOrder();
size_t instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount();
- EXPECT_EQ(instr_replaced_by_clones_count, 13u);
+ EXPECT_EQ(instr_replaced_by_clones_count, 14u);
EXPECT_TRUE(CheckGraph());
visitor.VisitReversePostOrder();
instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount();
- EXPECT_EQ(instr_replaced_by_clones_count, 26u);
+ EXPECT_EQ(instr_replaced_by_clones_count, 28u);
EXPECT_TRUE(CheckGraph());
HSuspendCheck* new_suspend_check = header->GetLoopInformation()->GetSuspendCheck();
@@ -133,12 +109,10 @@ TEST_F(SuperblockClonerTest, IndividualInstrCloner) {
// Tests SuperblockCloner::CloneBasicBlocks - check instruction cloning and initial remapping of
// instructions' inputs.
TEST_F(SuperblockClonerTest, CloneBasicBlocks) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
ArenaAllocator* arena = GetAllocator();
HBasicBlock* return_block = InitGraphAndParameters();
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
+ auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
CreateBasicLoopDataFlow(header, loop_body);
graph_->BuildDominatorTree();
ASSERT_TRUE(CheckGraph());
@@ -214,12 +188,10 @@ TEST_F(SuperblockClonerTest, CloneBasicBlocks) {
// SuperblockCloner::CleanUpControlFlow - checks algorithms of local adjustments of the control
// flow.
TEST_F(SuperblockClonerTest, AdjustControlFlowInfo) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
ArenaAllocator* arena = GetAllocator();
HBasicBlock* return_block = InitGraphAndParameters();
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
+ auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
CreateBasicLoopDataFlow(header, loop_body);
graph_->BuildDominatorTree();
ASSERT_TRUE(CheckGraph());
@@ -253,12 +225,10 @@ TEST_F(SuperblockClonerTest, AdjustControlFlowInfo) {
// Tests IsSubgraphConnected function for negative case.
TEST_F(SuperblockClonerTest, IsGraphConnected) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
ArenaAllocator* arena = GetAllocator();
HBasicBlock* return_block = InitGraphAndParameters();
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
+ auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
CreateBasicLoopDataFlow(header, loop_body);
HBasicBlock* unreachable_block = AddNewBlock();
@@ -277,11 +247,8 @@ TEST_F(SuperblockClonerTest, IsGraphConnected) {
//
// See an ASCII graphics example near LoopClonerHelper::DoPeeling.
TEST_F(SuperblockClonerTest, LoopPeeling) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
-
HBasicBlock* return_block = InitGraphAndParameters();
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
+ auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
CreateBasicLoopDataFlow(header, loop_body);
graph_->BuildDominatorTree();
EXPECT_TRUE(CheckGraph());
@@ -314,11 +281,8 @@ TEST_F(SuperblockClonerTest, LoopPeeling) {
//
// See an ASCII graphics example near LoopClonerHelper::DoUnrolling.
TEST_F(SuperblockClonerTest, LoopUnrolling) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
-
HBasicBlock* return_block = InitGraphAndParameters();
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
+ auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
CreateBasicLoopDataFlow(header, loop_body);
graph_->BuildDominatorTree();
EXPECT_TRUE(CheckGraph());
@@ -351,11 +315,8 @@ TEST_F(SuperblockClonerTest, LoopUnrolling) {
//
// See an ASCII graphics example near LoopClonerHelper::DoVersioning.
TEST_F(SuperblockClonerTest, LoopVersioning) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
-
HBasicBlock* return_block = InitGraphAndParameters();
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
+ auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
CreateBasicLoopDataFlow(header, loop_body);
graph_->BuildDominatorTree();
EXPECT_TRUE(CheckGraph());
@@ -399,11 +360,8 @@ TEST_F(SuperblockClonerTest, LoopVersioning) {
// Checks that loop unrolling works fine for a loop with multiple back edges. Tests that after
// the transformation the loop has a single preheader.
TEST_F(SuperblockClonerTest, LoopPeelingMultipleBackEdges) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
-
HBasicBlock* return_block = InitGraphAndParameters();
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
+ auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
CreateBasicLoopDataFlow(header, loop_body);
// Transform a basic loop to have multiple back edges.
@@ -450,42 +408,36 @@ static void CheckLoopStructureForLoopPeelingNested(HBasicBlock* loop1_header,
}
TEST_F(SuperblockClonerTest, LoopPeelingNested) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
-
HBasicBlock* return_block = InitGraphAndParameters();
// Create the following nested structure of loops
// Headers: 1 2 3
// [ ], [ [ ] ]
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop1_header = header;
+ auto [preheader1, header1, body1] = CreateWhileLoop(return_block);
+ CreateBasicLoopDataFlow(header1, body1);
- CreateBasicLoopControlFlow(header, return_block, &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop2_header = header;
+ auto [preheader2, header2, body2_end] = CreateWhileLoop(return_block);
+ CreateBasicLoopDataFlow(header2, body2_end);
- CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop3_header = header;
+ auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
+ CreateBasicLoopDataFlow(header3, body3);
graph_->BuildDominatorTree();
EXPECT_TRUE(CheckGraph());
- HLoopInformation* loop2_info_before = loop2_header->GetLoopInformation();
- HLoopInformation* loop3_info_before = loop3_header->GetLoopInformation();
+ HLoopInformation* loop2_info_before = header2->GetLoopInformation();
+ HLoopInformation* loop3_info_before = header3->GetLoopInformation();
// Check nested loops structure.
- CheckLoopStructureForLoopPeelingNested(loop1_header, loop2_header, loop3_header);
- LoopClonerSimpleHelper helper(loop1_header->GetLoopInformation(), /* induction_range= */ nullptr);
+ CheckLoopStructureForLoopPeelingNested(header1, header2, header3);
+ LoopClonerSimpleHelper helper(header1->GetLoopInformation(), /* induction_range= */ nullptr);
helper.DoPeeling();
// Check that nested loops structure has not changed after the transformation.
- CheckLoopStructureForLoopPeelingNested(loop1_header, loop2_header, loop3_header);
+ CheckLoopStructureForLoopPeelingNested(header1, header2, header3);
// Test that the loop info is preserved.
- EXPECT_EQ(loop2_info_before, loop2_header->GetLoopInformation());
- EXPECT_EQ(loop3_info_before, loop3_header->GetLoopInformation());
+ EXPECT_EQ(loop2_info_before, header2->GetLoopInformation());
+ EXPECT_EQ(loop3_info_before, header3->GetLoopInformation());
EXPECT_EQ(loop3_info_before->GetPreHeader()->GetLoopInformation(), loop2_info_before);
EXPECT_EQ(loop2_info_before->GetPreHeader()->GetLoopInformation(), nullptr);
@@ -497,46 +449,39 @@ TEST_F(SuperblockClonerTest, LoopPeelingNested) {
// Checks that the loop population is correctly propagated after an inner loop is peeled.
TEST_F(SuperblockClonerTest, OuterLoopPopulationAfterInnerPeeled) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
-
HBasicBlock* return_block = InitGraphAndParameters();
// Create the following nested structure of loops
// Headers: 1 2 3 4
// [ [ [ ] ] ], [ ]
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop1_header = header;
+ auto [preheader1, header1, body1_end] = CreateWhileLoop(return_block);
+ CreateBasicLoopDataFlow(header1, body1_end);
- CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop2_header = header;
+ auto [preheader2, header2, body2_end] = CreateWhileLoop(body1_end);
+ CreateBasicLoopDataFlow(header2, body2_end);
- CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop3_header = header;
+ auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
+ CreateBasicLoopDataFlow(header3, body3);
- CreateBasicLoopControlFlow(loop1_header, return_block, &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop4_header = header;
+ auto [preheader4, header4, body4] = CreateWhileLoop(return_block);
+ CreateBasicLoopDataFlow(header4, body4);
graph_->BuildDominatorTree();
EXPECT_TRUE(CheckGraph());
- LoopClonerSimpleHelper helper(loop3_header->GetLoopInformation(), /* induction_range= */ nullptr);
+ LoopClonerSimpleHelper helper(header3->GetLoopInformation(), /* induction_range= */ nullptr);
helper.DoPeeling();
- HLoopInformation* loop1 = loop1_header->GetLoopInformation();
- HLoopInformation* loop2 = loop2_header->GetLoopInformation();
- HLoopInformation* loop3 = loop3_header->GetLoopInformation();
- HLoopInformation* loop4 = loop4_header->GetLoopInformation();
+ HLoopInformation* loop1 = header1->GetLoopInformation();
+ HLoopInformation* loop2 = header2->GetLoopInformation();
+ HLoopInformation* loop3 = header3->GetLoopInformation();
+ HLoopInformation* loop4 = header4->GetLoopInformation();
- EXPECT_TRUE(loop1->Contains(*loop2_header));
- EXPECT_TRUE(loop1->Contains(*loop3_header));
- EXPECT_TRUE(loop1->Contains(*loop3_header->GetLoopInformation()->GetPreHeader()));
+ EXPECT_TRUE(loop1->Contains(*header2));
+ EXPECT_TRUE(loop1->Contains(*header3));
+ EXPECT_TRUE(loop1->Contains(*header3->GetLoopInformation()->GetPreHeader()));
// Check that loop4 info has not been touched after local run of AnalyzeLoops.
- EXPECT_EQ(loop4, loop4_header->GetLoopInformation());
+ EXPECT_EQ(loop4, header4->GetLoopInformation());
EXPECT_TRUE(loop1->IsIn(*loop1));
EXPECT_TRUE(loop2->IsIn(*loop1));
@@ -554,45 +499,39 @@ TEST_F(SuperblockClonerTest, OuterLoopPopulationAfterInnerPeeled) {
// Checks the case when inner loop have an exit not to its immediate outer_loop but some other loop
// in the hierarchy. Loop population information must be valid after loop peeling.
TEST_F(SuperblockClonerTest, NestedCaseExitToOutermost) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
-
HBasicBlock* return_block = InitGraphAndParameters();
// Create the following nested structure of loops then peel loop3.
// Headers: 1 2 3
// [ [ [ ] ] ]
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop1_header = header;
- HBasicBlock* loop_body1 = loop_body;
+ auto [preheader1, header1, body1_end] = CreateWhileLoop(return_block);
+ CreateBasicLoopDataFlow(header1, body1_end);
- CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
+ auto [preheader2, header2, body2_end] = CreateWhileLoop(body1_end);
+ CreateBasicLoopDataFlow(header2, body2_end);
- CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop3_header = header;
- HBasicBlock* loop_body3 = loop_body;
+ auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
+ CreateBasicLoopDataFlow(header3, body3);
// Change the loop3 - insert an exit which leads to loop1.
HBasicBlock* loop3_extra_if_block = AddNewBlock();
MakeIf(loop3_extra_if_block, param_);
- loop3_header->ReplaceSuccessor(loop_body3, loop3_extra_if_block);
- loop3_extra_if_block->AddSuccessor(loop_body1); // Long exit.
- loop3_extra_if_block->AddSuccessor(loop_body3);
+ header3->ReplaceSuccessor(body3, loop3_extra_if_block);
+ // Note: After this, both edges to `body1_end` shall be critical edges.
+ loop3_extra_if_block->AddSuccessor(body1_end); // Long exit.
+ loop3_extra_if_block->AddSuccessor(body3);
graph_->BuildDominatorTree();
EXPECT_TRUE(CheckGraph());
HBasicBlock* loop3_long_exit = loop3_extra_if_block->GetSuccessors()[0];
- EXPECT_TRUE(loop1_header->GetLoopInformation()->Contains(*loop3_long_exit));
+ EXPECT_TRUE(header1->GetLoopInformation()->Contains(*loop3_long_exit));
- LoopClonerSimpleHelper helper(loop3_header->GetLoopInformation(), /* induction_range= */ nullptr);
+ LoopClonerSimpleHelper helper(header3->GetLoopInformation(), /* induction_range= */ nullptr);
helper.DoPeeling();
- HLoopInformation* loop1 = loop1_header->GetLoopInformation();
+ HLoopInformation* loop1 = header1->GetLoopInformation();
// Check that after the transformation the local area for CF adjustments has been chosen
// correctly and loop population has been updated.
loop3_long_exit = loop3_extra_if_block->GetSuccessors()[0];
@@ -600,19 +539,17 @@ TEST_F(SuperblockClonerTest, NestedCaseExitToOutermost) {
EXPECT_EQ(helper.GetRegionToBeAdjusted(), loop1);
- EXPECT_TRUE(loop1->Contains(*loop3_header));
- EXPECT_TRUE(loop1->Contains(*loop3_header->GetLoopInformation()->GetPreHeader()));
+ EXPECT_TRUE(loop1->Contains(*header3));
+ EXPECT_TRUE(loop1->Contains(*header3->GetLoopInformation()->GetPreHeader()));
EXPECT_TRUE(CheckGraph());
}
TEST_F(SuperblockClonerTest, FastCaseCheck) {
- HBasicBlock* header = nullptr;
- HBasicBlock* loop_body = nullptr;
ArenaAllocator* arena = GetAllocator();
HBasicBlock* return_block = InitGraphAndParameters();
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
+ auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
CreateBasicLoopDataFlow(header, loop_body);
graph_->BuildDominatorTree();
@@ -633,7 +570,7 @@ TEST_F(SuperblockClonerTest, FastCaseCheck) {
&remap_incoming);
// Insert some extra nodes and edges.
- HBasicBlock* preheader = loop_info->GetPreHeader();
+ ASSERT_EQ(preheader, loop_info->GetPreHeader());
orig_bb_set.SetBit(preheader->GetBlockId());
// Adjust incoming edges.
@@ -671,34 +608,29 @@ TEST_F(SuperblockClonerTest, FindCommonLoop) {
// Create the following nested structure of loops
// Headers: 1 2 3 4 5
// [ [ [ ] ], [ ] ], [ ]
- CreateBasicLoopControlFlow(entry_block_, return_block, &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop1_header = header;
+ auto [preheader1, header1, body1_end] = CreateWhileLoop(return_block);
+ CreateBasicLoopDataFlow(header1, body1_end);
- CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop2_header = header;
+ auto [preheader2, header2, body2_end] = CreateWhileLoop(body1_end);
+ CreateBasicLoopDataFlow(header2, body2_end);
- CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop3_header = header;
+ auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
+ CreateBasicLoopDataFlow(header3, body3);
- CreateBasicLoopControlFlow(loop2_header, loop2_header->GetSuccessors()[0], &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop4_header = header;
+ auto [preheader4, header4, body4] = CreateWhileLoop(body1_end);
+ CreateBasicLoopDataFlow(header4, body4);
- CreateBasicLoopControlFlow(loop1_header, return_block, &header, &loop_body);
- CreateBasicLoopDataFlow(header, loop_body);
- HBasicBlock* loop5_header = header;
+ auto [preheader5, header5, body5] = CreateWhileLoop(return_block);
+ CreateBasicLoopDataFlow(header5, body5);
graph_->BuildDominatorTree();
EXPECT_TRUE(CheckGraph());
- HLoopInformation* loop1 = loop1_header->GetLoopInformation();
- HLoopInformation* loop2 = loop2_header->GetLoopInformation();
- HLoopInformation* loop3 = loop3_header->GetLoopInformation();
- HLoopInformation* loop4 = loop4_header->GetLoopInformation();
- HLoopInformation* loop5 = loop5_header->GetLoopInformation();
+ HLoopInformation* loop1 = header1->GetLoopInformation();
+ HLoopInformation* loop2 = header2->GetLoopInformation();
+ HLoopInformation* loop3 = header3->GetLoopInformation();
+ HLoopInformation* loop4 = header4->GetLoopInformation();
+ HLoopInformation* loop5 = header5->GetLoopInformation();
EXPECT_TRUE(loop1->IsIn(*loop1));
EXPECT_TRUE(loop2->IsIn(*loop1));
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-20 04:46:19 +0000