/*
* Copyright (C) 2014 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 "base/arena_allocator.h"
#include "builder.h"
#include "dex_file.h"
#include "dex_instruction.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
#include "ssa_liveness_analysis.h"
#include "pretty_printer.h"
#include "gtest/gtest.h"
namespace art {
static HGraph* TestCode(const uint16_t* data, ArenaAllocator* allocator) {
HGraph* graph = CreateGraph(allocator);
HGraphBuilder builder(graph);
const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
builder.BuildGraph(*item);
graph->BuildDominatorTree();
graph->AnalyzeNaturalLoops();
return graph;
}
TEST(FindLoopsTest, CFG1) {
// Constant is not used.
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::RETURN_VOID);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
}
}
TEST(FindLoopsTest, CFG2) {
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::RETURN);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
}
}
TEST(FindLoopsTest, CFG3) {
const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
Instruction::CONST_4 | 3 << 12 | 0,
Instruction::CONST_4 | 4 << 12 | 1 << 8,
Instruction::ADD_INT_2ADDR | 1 << 12,
Instruction::GOTO | 0x100,
Instruction::RETURN);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
}
}
TEST(FindLoopsTest, CFG4) {
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::IF_EQ, 4,
Instruction::CONST_4 | 4 << 12 | 0,
Instruction::GOTO | 0x200,
Instruction::CONST_4 | 5 << 12 | 0,
Instruction::RETURN | 0 << 8);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
}
}
TEST(FindLoopsTest, CFG5) {
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::IF_EQ, 3,
Instruction::CONST_4 | 4 << 12 | 0,
Instruction::RETURN | 0 << 8);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
ASSERT_EQ(graph->GetBlocks().Get(i)->GetLoopInformation(), nullptr);
}
}
static void TestBlock(HGraph* graph,
int block_id,
bool is_loop_header,
int parent_loop_header_id,
const int* blocks_in_loop = nullptr,
size_t number_of_blocks = 0) {
HBasicBlock* block = graph->GetBlocks().Get(block_id);
ASSERT_EQ(block->IsLoopHeader(), is_loop_header);
if (parent_loop_header_id == -1) {
ASSERT_EQ(block->GetLoopInformation(), nullptr);
} else {
ASSERT_EQ(block->GetLoopInformation()->GetHeader()->GetBlockId(), parent_loop_header_id);
}
if (blocks_in_loop != nullptr) {
HLoopInformation* info = block->GetLoopInformation();
const BitVector& blocks = info->GetBlocks();
ASSERT_EQ(blocks.NumSetBits(), number_of_blocks);
for (size_t i = 0; i < number_of_blocks; ++i) {
ASSERT_TRUE(blocks.IsBitSet(blocks_in_loop[i]));
}
} else {
ASSERT_FALSE(block->IsLoopHeader());
}
}
TEST(FindLoopsTest, Loop1) {
// Simple loop with one preheader and one back edge.
// var a = 0;
// while (a == a) {
// }
// return;
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::IF_EQ, 3,
Instruction::GOTO | 0xFE00,
Instruction::RETURN_VOID);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
TestBlock(graph, 0, false, -1); // entry block
TestBlock(graph, 1, false, -1); // pre header
const int blocks2[] = {2, 3};
TestBlock(graph, 2, true, 2, blocks2, 2); // loop header
TestBlock(graph, 3, false, 2); // block in loop
TestBlock(graph, 4, false, -1); // return block
TestBlock(graph, 5, false, -1); // exit block
}
TEST(FindLoopsTest, Loop2) {
// Make sure we support a preheader of a loop not being the first predecessor
// in the predecessor list of the header.
// var a = 0;
// while (a == a) {
// }
// return a;
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::GOTO | 0x400,
Instruction::IF_EQ, 4,
Instruction::GOTO | 0xFE00,
Instruction::GOTO | 0xFD00,
Instruction::RETURN | 0 << 8);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
TestBlock(graph, 0, false, -1); // entry block
TestBlock(graph, 1, false, -1); // goto block
const int blocks2[] = {2, 3};
TestBlock(graph, 2, true, 2, blocks2, 2); // loop header
TestBlock(graph, 3, false, 2); // block in loop
TestBlock(graph, 4, false, -1); // pre header
TestBlock(graph, 5, false, -1); // return block
TestBlock(graph, 6, false, -1); // exit block
}
TEST(FindLoopsTest, Loop3) {
// Make sure we create a preheader of a loop when a header originally has two
// incoming blocks and one back edge.
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::IF_EQ, 3,
Instruction::GOTO | 0x100,
Instruction::IF_EQ, 3,
Instruction::GOTO | 0xFE00,
Instruction::RETURN | 0 << 8);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
TestBlock(graph, 0, false, -1); // entry block
TestBlock(graph, 1, false, -1); // goto block
TestBlock(graph, 2, false, -1);
const int blocks2[] = {3, 4};
TestBlock(graph, 3, true, 3, blocks2, 2); // loop header
TestBlock(graph, 4, false, 3); // block in loop
TestBlock(graph, 5, false, -1); // pre header
TestBlock(graph, 6, false, -1); // return block
TestBlock(graph, 7, false, -1); // exit block
TestBlock(graph, 8, false, -1); // synthesized pre header
}
TEST(FindLoopsTest, Loop4) {
// Test loop with originally two back edges.
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::IF_EQ, 6,
Instruction::IF_EQ, 3,
Instruction::GOTO | 0xFC00,
Instruction::GOTO | 0xFB00,
Instruction::RETURN | 0 << 8);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
TestBlock(graph, 0, false, -1); // entry block
TestBlock(graph, 1, false, -1); // pre header
const int blocks2[] = {2, 3, 4, 5};
TestBlock(graph, 2, true, 2, blocks2, arraysize(blocks2)); // loop header
TestBlock(graph, 3, false, 2); // block in loop
TestBlock(graph, 4, false, 2); // back edge
TestBlock(graph, 5, false, 2); // back edge
TestBlock(graph, 6, false, -1); // return block
TestBlock(graph, 7, false, -1); // exit block
}
TEST(FindLoopsTest, Loop5) {
// Test loop with two exit edges.
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::IF_EQ, 6,
Instruction::IF_EQ, 3,
Instruction::GOTO | 0x0200,
Instruction::GOTO | 0xFB00,
Instruction::RETURN | 0 << 8);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
TestBlock(graph, 0, false, -1); // entry block
TestBlock(graph, 1, false, -1); // pre header
const int blocks2[] = {2, 3, 5};
TestBlock(graph, 2, true, 2, blocks2, 3); // loop header
TestBlock(graph, 3, false, 2); // block in loop
TestBlock(graph, 4, false, -1); // loop exit
TestBlock(graph, 5, false, 2); // back edge
TestBlock(graph, 6, false, -1); // return block
TestBlock(graph, 7, false, -1); // exit block
TestBlock(graph, 8, false, -1); // synthesized block at the loop exit
}
TEST(FindLoopsTest, InnerLoop) {
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::IF_EQ, 6,
Instruction::IF_EQ, 3,
Instruction::GOTO | 0xFE00, // inner loop
Instruction::GOTO | 0xFB00,
Instruction::RETURN | 0 << 8);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
TestBlock(graph, 0, false, -1); // entry block
TestBlock(graph, 1, false, -1); // pre header of outer loop
const int blocks2[] = {2, 3, 4, 5, 8};
TestBlock(graph, 2, true, 2, blocks2, 5); // outer loop header
const int blocks3[] = {3, 4};
TestBlock(graph, 3, true, 3, blocks3, 2); // inner loop header
TestBlock(graph, 4, false, 3); // back edge on inner loop
TestBlock(graph, 5, false, 2); // back edge on outer loop
TestBlock(graph, 6, false, -1); // return block
TestBlock(graph, 7, false, -1); // exit block
TestBlock(graph, 8, false, 2); // synthesized block as pre header of inner loop
ASSERT_TRUE(graph->GetBlocks().Get(3)->GetLoopInformation()->IsIn(
*graph->GetBlocks().Get(2)->GetLoopInformation()));
ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
*graph->GetBlocks().Get(3)->GetLoopInformation()));
}
TEST(FindLoopsTest, TwoLoops) {
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::IF_EQ, 3,
Instruction::GOTO | 0xFE00, // first loop
Instruction::IF_EQ, 3,
Instruction::GOTO | 0xFE00, // second loop
Instruction::RETURN | 0 << 8);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
TestBlock(graph, 0, false, -1); // entry block
TestBlock(graph, 1, false, -1); // pre header of first loop
const int blocks2[] = {2, 3};
TestBlock(graph, 2, true, 2, blocks2, 2); // first loop header
TestBlock(graph, 3, false, 2); // back edge of first loop
const int blocks4[] = {4, 5};
TestBlock(graph, 4, true, 4, blocks4, 2); // second loop header
TestBlock(graph, 5, false, 4); // back edge of second loop
TestBlock(graph, 6, false, -1); // return block
TestBlock(graph, 7, false, -1); // exit block
ASSERT_FALSE(graph->GetBlocks().Get(4)->GetLoopInformation()->IsIn(
*graph->GetBlocks().Get(2)->GetLoopInformation()));
ASSERT_FALSE(graph->GetBlocks().Get(2)->GetLoopInformation()->IsIn(
*graph->GetBlocks().Get(4)->GetLoopInformation()));
}
TEST(FindLoopsTest, NonNaturalLoop) {
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::IF_EQ, 3,
Instruction::GOTO | 0x0100,
Instruction::IF_EQ, 3,
Instruction::GOTO | 0xFD00,
Instruction::RETURN | 0 << 8);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
ASSERT_TRUE(graph->GetBlocks().Get(3)->IsLoopHeader());
HLoopInformation* info = graph->GetBlocks().Get(3)->GetLoopInformation();
ASSERT_FALSE(info->GetHeader()->Dominates(info->GetBackEdges().Get(0)));
}
TEST(FindLoopsTest, DoWhileLoop) {
const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
Instruction::CONST_4 | 0 | 0,
Instruction::GOTO | 0x0100,
Instruction::IF_EQ, 0xFFFF,
Instruction::RETURN | 0 << 8);
ArenaPool arena;
ArenaAllocator allocator(&arena);
HGraph* graph = TestCode(data, &allocator);
TestBlock(graph, 0, false, -1); // entry block
TestBlock(graph, 1, false, -1); // pre header of first loop
const int blocks2[] = {2, 3, 6};
TestBlock(graph, 2, true, 2, blocks2, 3); // loop header
TestBlock(graph, 3, false, 2); // back edge of first loop
TestBlock(graph, 4, false, -1); // return block
TestBlock(graph, 5, false, -1); // exit block
TestBlock(graph, 6, false, 2); // synthesized block to avoid a critical edge
}
} // namespace art