Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2014 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #include <fstream> |
| 18 | |
| 19 | #include "base/stringprintf.h" |
| 20 | #include "builder.h" |
| 21 | #include "dex_file.h" |
| 22 | #include "dex_instruction.h" |
| 23 | #include "graph_visualizer.h" |
| 24 | #include "nodes.h" |
| 25 | #include "optimizing_unit_test.h" |
| 26 | #include "pretty_printer.h" |
| 27 | #include "ssa_builder.h" |
| 28 | #include "ssa_liveness_analysis.h" |
| 29 | #include "utils/arena_allocator.h" |
| 30 | |
| 31 | #include "gtest/gtest.h" |
| 32 | |
| 33 | namespace art { |
| 34 | |
| 35 | static void TestCode(const uint16_t* data, const int* expected_order, size_t number_of_blocks) { |
| 36 | ArenaPool pool; |
| 37 | ArenaAllocator allocator(&pool); |
| 38 | HGraphBuilder builder(&allocator); |
| 39 | const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); |
| 40 | HGraph* graph = builder.BuildGraph(*item); |
| 41 | ASSERT_NE(graph, nullptr); |
| 42 | |
| 43 | graph->BuildDominatorTree(); |
| 44 | graph->FindNaturalLoops(); |
| 45 | SsaLivenessAnalysis liveness(*graph); |
| 46 | liveness.Analyze(); |
| 47 | |
| 48 | ASSERT_EQ(liveness.GetLinearPostOrder().Size(), number_of_blocks); |
| 49 | for (size_t i = 0; i < number_of_blocks; ++i) { |
| 50 | ASSERT_EQ(liveness.GetLinearPostOrder().Get(number_of_blocks - i - 1)->GetBlockId(), |
| 51 | expected_order[i]); |
| 52 | } |
| 53 | } |
| 54 | |
| 55 | TEST(LinearizeTest, CFG1) { |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 56 | // Structure of this graph (+ are back edges) |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 57 | // Block0 |
| 58 | // | |
| 59 | // Block1 |
| 60 | // | |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 61 | // Block2 ++++++ |
| 62 | // / \ + |
| 63 | // Block5 Block7 + |
| 64 | // | | + |
| 65 | // Block6 Block3 + |
| 66 | // + / \ + |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 67 | // Block4 Block8 |
| 68 | |
| 69 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 70 | Instruction::CONST_4 | 0 | 0, |
| 71 | Instruction::IF_EQ, 5, |
| 72 | Instruction::IF_EQ, 0xFFFE, |
| 73 | Instruction::GOTO | 0xFE00, |
| 74 | Instruction::RETURN_VOID); |
| 75 | |
| 76 | const int blocks[] = {0, 1, 2, 7, 3, 4, 8, 5, 6}; |
| 77 | TestCode(data, blocks, 9); |
| 78 | } |
| 79 | |
| 80 | TEST(LinearizeTest, CFG2) { |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 81 | // Structure of this graph (+ are back edges) |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 82 | // Block0 |
| 83 | // | |
| 84 | // Block1 |
| 85 | // | |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 86 | // Block2 ++++++ |
| 87 | // / \ + |
| 88 | // Block3 Block7 + |
| 89 | // | | + |
| 90 | // Block6 Block4 + |
| 91 | // + / \ + |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 92 | // Block5 Block8 |
| 93 | |
| 94 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 95 | Instruction::CONST_4 | 0 | 0, |
| 96 | Instruction::IF_EQ, 3, |
| 97 | Instruction::RETURN_VOID, |
| 98 | Instruction::IF_EQ, 0xFFFD, |
| 99 | Instruction::GOTO | 0xFE00); |
| 100 | |
| 101 | const int blocks[] = {0, 1, 2, 7, 4, 5, 8, 3, 6}; |
| 102 | TestCode(data, blocks, 9); |
| 103 | } |
| 104 | |
| 105 | TEST(LinearizeTest, CFG3) { |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 106 | // Structure of this graph (+ are back edges) |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 107 | // Block0 |
| 108 | // | |
| 109 | // Block1 |
| 110 | // | |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 111 | // Block2 ++++++ |
| 112 | // / \ + |
| 113 | // Block3 Block8 + |
| 114 | // | | + |
| 115 | // Block7 Block5 + |
| 116 | // / + \ + |
| 117 | // Block6 + Block9 |
| 118 | // | + |
| 119 | // Block4 ++ |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 120 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 121 | Instruction::CONST_4 | 0 | 0, |
| 122 | Instruction::IF_EQ, 4, |
| 123 | Instruction::RETURN_VOID, |
| 124 | Instruction::GOTO | 0x0100, |
| 125 | Instruction::IF_EQ, 0xFFFC, |
| 126 | Instruction::GOTO | 0xFD00); |
| 127 | |
| 128 | const int blocks[] = {0, 1, 2, 8, 5, 6, 4, 9, 3, 7}; |
| 129 | TestCode(data, blocks, 10); |
| 130 | } |
| 131 | |
| 132 | TEST(LinearizeTest, CFG4) { |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 133 | /* Structure of this graph (+ are back edges) |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 134 | // Block0 |
| 135 | // | |
| 136 | // Block1 |
| 137 | // | |
| 138 | // Block2 |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 139 | // / + \ |
| 140 | // Block6 + Block8 |
| 141 | // | + | |
| 142 | // Block7 + Block3 +++++++ |
| 143 | // + / \ + |
| 144 | // Block9 Block10 + |
| 145 | // | + |
| 146 | // Block4 + |
| 147 | // + / \ + |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 148 | // Block5 Block11 |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 149 | */ |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 150 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 151 | Instruction::CONST_4 | 0 | 0, |
| 152 | Instruction::IF_EQ, 7, |
| 153 | Instruction::IF_EQ, 0xFFFE, |
| 154 | Instruction::IF_EQ, 0xFFFE, |
| 155 | Instruction::GOTO | 0xFE00, |
| 156 | Instruction::RETURN_VOID); |
| 157 | |
| 158 | const int blocks[] = {0, 1, 2, 8, 3, 10, 4, 5, 11, 9, 6, 7}; |
| 159 | TestCode(data, blocks, 12); |
| 160 | } |
| 161 | |
| 162 | TEST(LinearizeTest, CFG5) { |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 163 | /* Structure of this graph (+ are back edges) |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 164 | // Block0 |
| 165 | // | |
| 166 | // Block1 |
| 167 | // | |
| 168 | // Block2 |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 169 | // / + \ |
| 170 | // Block3 + Block8 |
| 171 | // | + | |
| 172 | // Block7 + Block4 +++++++ |
| 173 | // + / \ + |
| 174 | // Block9 Block10 + |
| 175 | // | + |
| 176 | // Block5 + |
| 177 | // +/ \ + |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 178 | // Block6 Block11 |
Nicolas Geoffray | 8f1a4d4 | 2014-05-16 09:36:00 +0100 | [diff] [blame^] | 179 | */ |
Nicolas Geoffray | 0d3f578 | 2014-05-14 09:43:38 +0100 | [diff] [blame] | 180 | const uint16_t data[] = ONE_REGISTER_CODE_ITEM( |
| 181 | Instruction::CONST_4 | 0 | 0, |
| 182 | Instruction::IF_EQ, 3, |
| 183 | Instruction::RETURN_VOID, |
| 184 | Instruction::IF_EQ, 0xFFFD, |
| 185 | Instruction::IF_EQ, 0xFFFE, |
| 186 | Instruction::GOTO | 0xFE00); |
| 187 | |
| 188 | const int blocks[] = {0, 1, 2, 8, 4, 10, 5, 6, 11, 9, 3, 7}; |
| 189 | TestCode(data, blocks, 12); |
| 190 | } |
| 191 | |
| 192 | } // namespace art |