Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +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 | |
Mathieu Chartier | b666f48 | 2015-02-18 14:33:14 -0800 | [diff] [blame] | 17 | #include "base/arena_allocator.h" |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 18 | #include "builder.h" |
David Sehr | 9e734c7 | 2018-01-04 17:56:19 -0800 | [diff] [blame] | 19 | #include "dex/dex_file.h" |
| 20 | #include "dex/dex_instruction.h" |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 21 | #include "nodes.h" |
| 22 | #include "optimizing_unit_test.h" |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 23 | #include "pretty_printer.h" |
Andreas Gampe | 8cf9cb3 | 2017-07-19 09:28:38 -0700 | [diff] [blame] | 24 | #include "ssa_liveness_analysis.h" |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 25 | |
| 26 | #include "gtest/gtest.h" |
| 27 | |
| 28 | namespace art { |
| 29 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 30 | class FindLoopsTest : public OptimizingUnitTest {}; |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 31 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 32 | TEST_F(FindLoopsTest, CFG1) { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 33 | // Constant is not used. |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 34 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 35 | Instruction::CONST_4 | 0 | 0, |
| 36 | Instruction::RETURN_VOID); |
| 37 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 38 | HGraph* graph = CreateCFG(data); |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 39 | for (HBasicBlock* block : graph->GetBlocks()) { |
| 40 | ASSERT_EQ(block->GetLoopInformation(), nullptr); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 41 | } |
| 42 | } |
| 43 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 44 | TEST_F(FindLoopsTest, CFG2) { |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 45 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 46 | Instruction::CONST_4 | 0 | 0, |
| 47 | Instruction::RETURN); |
| 48 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 49 | HGraph* graph = CreateCFG(data); |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 50 | for (HBasicBlock* block : graph->GetBlocks()) { |
| 51 | ASSERT_EQ(block->GetLoopInformation(), nullptr); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 52 | } |
| 53 | } |
| 54 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 55 | TEST_F(FindLoopsTest, CFG3) { |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 56 | const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 57 | Instruction::CONST_4 | 3 << 12 | 0, |
| 58 | Instruction::CONST_4 | 4 << 12 | 1 << 8, |
| 59 | Instruction::ADD_INT_2ADDR | 1 << 12, |
| 60 | Instruction::GOTO | 0x100, |
| 61 | Instruction::RETURN); |
| 62 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 63 | HGraph* graph = CreateCFG(data); |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 64 | for (HBasicBlock* block : graph->GetBlocks()) { |
| 65 | ASSERT_EQ(block->GetLoopInformation(), nullptr); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 66 | } |
| 67 | } |
| 68 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 69 | TEST_F(FindLoopsTest, CFG4) { |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 70 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 71 | Instruction::CONST_4 | 0 | 0, |
| 72 | Instruction::IF_EQ, 4, |
| 73 | Instruction::CONST_4 | 4 << 12 | 0, |
| 74 | Instruction::GOTO | 0x200, |
| 75 | Instruction::CONST_4 | 5 << 12 | 0, |
| 76 | Instruction::RETURN | 0 << 8); |
| 77 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 78 | HGraph* graph = CreateCFG(data); |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 79 | for (HBasicBlock* block : graph->GetBlocks()) { |
| 80 | ASSERT_EQ(block->GetLoopInformation(), nullptr); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 81 | } |
| 82 | } |
| 83 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 84 | TEST_F(FindLoopsTest, CFG5) { |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 85 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 86 | Instruction::CONST_4 | 0 | 0, |
| 87 | Instruction::IF_EQ, 3, |
| 88 | Instruction::CONST_4 | 4 << 12 | 0, |
| 89 | Instruction::RETURN | 0 << 8); |
| 90 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 91 | HGraph* graph = CreateCFG(data); |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 92 | for (HBasicBlock* block : graph->GetBlocks()) { |
| 93 | ASSERT_EQ(block->GetLoopInformation(), nullptr); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 94 | } |
| 95 | } |
| 96 | |
| 97 | static void TestBlock(HGraph* graph, |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 98 | uint32_t block_id, |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 99 | bool is_loop_header, |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 100 | uint32_t parent_loop_header_id, |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 101 | const int* blocks_in_loop = nullptr, |
| 102 | size_t number_of_blocks = 0) { |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 103 | HBasicBlock* block = graph->GetBlocks()[block_id]; |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 104 | ASSERT_EQ(block->IsLoopHeader(), is_loop_header); |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 105 | if (parent_loop_header_id == kInvalidBlockId) { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 106 | ASSERT_EQ(block->GetLoopInformation(), nullptr); |
| 107 | } else { |
| 108 | ASSERT_EQ(block->GetLoopInformation()->GetHeader()->GetBlockId(), parent_loop_header_id); |
| 109 | } |
| 110 | |
| 111 | if (blocks_in_loop != nullptr) { |
| 112 | HLoopInformation* info = block->GetLoopInformation(); |
| 113 | const BitVector& blocks = info->GetBlocks(); |
| 114 | ASSERT_EQ(blocks.NumSetBits(), number_of_blocks); |
| 115 | for (size_t i = 0; i < number_of_blocks; ++i) { |
| 116 | ASSERT_TRUE(blocks.IsBitSet(blocks_in_loop[i])); |
| 117 | } |
| 118 | } else { |
| 119 | ASSERT_FALSE(block->IsLoopHeader()); |
| 120 | } |
| 121 | } |
| 122 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 123 | TEST_F(FindLoopsTest, Loop1) { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 124 | // Simple loop with one preheader and one back edge. |
| 125 | // var a = 0; |
| 126 | // while (a == a) { |
| 127 | // } |
| 128 | // return; |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 129 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 130 | Instruction::CONST_4 | 0 | 0, |
| 131 | Instruction::IF_EQ, 3, |
| 132 | Instruction::GOTO | 0xFE00, |
| 133 | Instruction::RETURN_VOID); |
| 134 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 135 | HGraph* graph = CreateCFG(data); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 136 | |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 137 | TestBlock(graph, 0, false, kInvalidBlockId); // entry block |
| 138 | TestBlock(graph, 1, false, kInvalidBlockId); // pre header |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 139 | const int blocks2[] = {2, 3}; |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 140 | TestBlock(graph, 2, true, 2, blocks2, 2); // loop header |
| 141 | TestBlock(graph, 3, false, 2); // block in loop |
| 142 | TestBlock(graph, 4, false, kInvalidBlockId); // return block |
| 143 | TestBlock(graph, 5, false, kInvalidBlockId); // exit block |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 144 | } |
| 145 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 146 | TEST_F(FindLoopsTest, Loop2) { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 147 | // Make sure we support a preheader of a loop not being the first predecessor |
| 148 | // in the predecessor list of the header. |
| 149 | // var a = 0; |
| 150 | // while (a == a) { |
| 151 | // } |
| 152 | // return a; |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 153 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 154 | Instruction::CONST_4 | 0 | 0, |
| 155 | Instruction::GOTO | 0x400, |
| 156 | Instruction::IF_EQ, 4, |
| 157 | Instruction::GOTO | 0xFE00, |
| 158 | Instruction::GOTO | 0xFD00, |
| 159 | Instruction::RETURN | 0 << 8); |
| 160 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 161 | HGraph* graph = CreateCFG(data); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 162 | |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 163 | TestBlock(graph, 0, false, kInvalidBlockId); // entry block |
| 164 | TestBlock(graph, 1, false, kInvalidBlockId); // goto block |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 165 | const int blocks2[] = {2, 3}; |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 166 | TestBlock(graph, 2, true, 2, blocks2, 2); // loop header |
| 167 | TestBlock(graph, 3, false, 2); // block in loop |
| 168 | TestBlock(graph, 4, false, kInvalidBlockId); // pre header |
| 169 | TestBlock(graph, 5, false, kInvalidBlockId); // return block |
| 170 | TestBlock(graph, 6, false, kInvalidBlockId); // exit block |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 171 | } |
| 172 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 173 | TEST_F(FindLoopsTest, Loop3) { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 174 | // Make sure we create a preheader of a loop when a header originally has two |
| 175 | // incoming blocks and one back edge. |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 176 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 177 | Instruction::CONST_4 | 0 | 0, |
| 178 | Instruction::IF_EQ, 3, |
| 179 | Instruction::GOTO | 0x100, |
| 180 | Instruction::IF_EQ, 3, |
| 181 | Instruction::GOTO | 0xFE00, |
| 182 | Instruction::RETURN | 0 << 8); |
| 183 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 184 | HGraph* graph = CreateCFG(data); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 185 | |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 186 | TestBlock(graph, 0, false, kInvalidBlockId); // entry block |
| 187 | TestBlock(graph, 1, false, kInvalidBlockId); // goto block |
| 188 | TestBlock(graph, 2, false, kInvalidBlockId); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 189 | const int blocks2[] = {3, 4}; |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 190 | TestBlock(graph, 3, true, 3, blocks2, 2); // loop header |
| 191 | TestBlock(graph, 4, false, 3); // block in loop |
| 192 | TestBlock(graph, 5, false, kInvalidBlockId); // pre header |
| 193 | TestBlock(graph, 6, false, kInvalidBlockId); // return block |
| 194 | TestBlock(graph, 7, false, kInvalidBlockId); // exit block |
| 195 | TestBlock(graph, 8, false, kInvalidBlockId); // synthesized pre header |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 196 | } |
| 197 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 198 | TEST_F(FindLoopsTest, Loop4) { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 199 | // Test loop with originally two back edges. |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 200 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 201 | Instruction::CONST_4 | 0 | 0, |
| 202 | Instruction::IF_EQ, 6, |
| 203 | Instruction::IF_EQ, 3, |
| 204 | Instruction::GOTO | 0xFC00, |
| 205 | Instruction::GOTO | 0xFB00, |
| 206 | Instruction::RETURN | 0 << 8); |
| 207 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 208 | HGraph* graph = CreateCFG(data); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 209 | |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 210 | TestBlock(graph, 0, false, kInvalidBlockId); // entry block |
| 211 | TestBlock(graph, 1, false, kInvalidBlockId); // pre header |
Nicolas Geoffray | db216f4 | 2015-05-05 17:02:20 +0100 | [diff] [blame] | 212 | const int blocks2[] = {2, 3, 4, 5}; |
| 213 | TestBlock(graph, 2, true, 2, blocks2, arraysize(blocks2)); // loop header |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 214 | TestBlock(graph, 3, false, 2); // block in loop |
| 215 | TestBlock(graph, 4, false, 2); // back edge |
| 216 | TestBlock(graph, 5, false, 2); // back edge |
| 217 | TestBlock(graph, 6, false, kInvalidBlockId); // return block |
| 218 | TestBlock(graph, 7, false, kInvalidBlockId); // exit block |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 219 | } |
| 220 | |
| 221 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 222 | TEST_F(FindLoopsTest, Loop5) { |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 223 | // Test loop with two exit edges. |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 224 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 225 | Instruction::CONST_4 | 0 | 0, |
| 226 | Instruction::IF_EQ, 6, |
| 227 | Instruction::IF_EQ, 3, |
| 228 | Instruction::GOTO | 0x0200, |
| 229 | Instruction::GOTO | 0xFB00, |
| 230 | Instruction::RETURN | 0 << 8); |
| 231 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 232 | HGraph* graph = CreateCFG(data); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 233 | |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 234 | TestBlock(graph, 0, false, kInvalidBlockId); // entry block |
| 235 | TestBlock(graph, 1, false, kInvalidBlockId); // pre header |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 236 | const int blocks2[] = {2, 3, 5}; |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 237 | TestBlock(graph, 2, true, 2, blocks2, 3); // loop header |
| 238 | TestBlock(graph, 3, false, 2); // block in loop |
| 239 | TestBlock(graph, 4, false, kInvalidBlockId); // loop exit |
| 240 | TestBlock(graph, 5, false, 2); // back edge |
| 241 | TestBlock(graph, 6, false, kInvalidBlockId); // return block |
| 242 | TestBlock(graph, 7, false, kInvalidBlockId); // exit block |
| 243 | TestBlock(graph, 8, false, kInvalidBlockId); // synthesized block at the loop exit |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 244 | } |
| 245 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 246 | TEST_F(FindLoopsTest, InnerLoop) { |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 247 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 248 | Instruction::CONST_4 | 0 | 0, |
| 249 | Instruction::IF_EQ, 6, |
| 250 | Instruction::IF_EQ, 3, |
| 251 | Instruction::GOTO | 0xFE00, // inner loop |
| 252 | Instruction::GOTO | 0xFB00, |
| 253 | Instruction::RETURN | 0 << 8); |
| 254 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 255 | HGraph* graph = CreateCFG(data); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 256 | |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 257 | TestBlock(graph, 0, false, kInvalidBlockId); // entry block |
| 258 | TestBlock(graph, 1, false, kInvalidBlockId); // pre header of outer loop |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 259 | const int blocks2[] = {2, 3, 4, 5, 8}; |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 260 | TestBlock(graph, 2, true, 2, blocks2, 5); // outer loop header |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 261 | const int blocks3[] = {3, 4}; |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 262 | TestBlock(graph, 3, true, 3, blocks3, 2); // inner loop header |
| 263 | TestBlock(graph, 4, false, 3); // back edge on inner loop |
| 264 | TestBlock(graph, 5, false, 2); // back edge on outer loop |
| 265 | TestBlock(graph, 6, false, kInvalidBlockId); // return block |
| 266 | TestBlock(graph, 7, false, kInvalidBlockId); // exit block |
| 267 | TestBlock(graph, 8, false, 2); // synthesized block as pre header of inner loop |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 268 | |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 269 | ASSERT_TRUE(graph->GetBlocks()[3]->GetLoopInformation()->IsIn( |
| 270 | *graph->GetBlocks()[2]->GetLoopInformation())); |
| 271 | ASSERT_FALSE(graph->GetBlocks()[2]->GetLoopInformation()->IsIn( |
| 272 | *graph->GetBlocks()[3]->GetLoopInformation())); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 273 | } |
| 274 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 275 | TEST_F(FindLoopsTest, TwoLoops) { |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 276 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 277 | Instruction::CONST_4 | 0 | 0, |
| 278 | Instruction::IF_EQ, 3, |
| 279 | Instruction::GOTO | 0xFE00, // first loop |
| 280 | Instruction::IF_EQ, 3, |
| 281 | Instruction::GOTO | 0xFE00, // second loop |
| 282 | Instruction::RETURN | 0 << 8); |
| 283 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 284 | HGraph* graph = CreateCFG(data); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 285 | |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 286 | TestBlock(graph, 0, false, kInvalidBlockId); // entry block |
| 287 | TestBlock(graph, 1, false, kInvalidBlockId); // pre header of first loop |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 288 | const int blocks2[] = {2, 3}; |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 289 | TestBlock(graph, 2, true, 2, blocks2, 2); // first loop header |
| 290 | TestBlock(graph, 3, false, 2); // back edge of first loop |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 291 | const int blocks4[] = {4, 5}; |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 292 | TestBlock(graph, 4, true, 4, blocks4, 2); // second loop header |
| 293 | TestBlock(graph, 5, false, 4); // back edge of second loop |
| 294 | TestBlock(graph, 6, false, kInvalidBlockId); // return block |
| 295 | TestBlock(graph, 7, false, kInvalidBlockId); // exit block |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 296 | |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 297 | ASSERT_FALSE(graph->GetBlocks()[4]->GetLoopInformation()->IsIn( |
| 298 | *graph->GetBlocks()[2]->GetLoopInformation())); |
| 299 | ASSERT_FALSE(graph->GetBlocks()[2]->GetLoopInformation()->IsIn( |
| 300 | *graph->GetBlocks()[4]->GetLoopInformation())); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 301 | } |
| 302 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 303 | TEST_F(FindLoopsTest, NonNaturalLoop) { |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 304 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 305 | Instruction::CONST_4 | 0 | 0, |
| 306 | Instruction::IF_EQ, 3, |
| 307 | Instruction::GOTO | 0x0100, |
| 308 | Instruction::IF_EQ, 3, |
| 309 | Instruction::GOTO | 0xFD00, |
| 310 | Instruction::RETURN | 0 << 8); |
| 311 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 312 | HGraph* graph = CreateCFG(data); |
Vladimir Marko | ec7802a | 2015-10-01 20:57:57 +0100 | [diff] [blame] | 313 | ASSERT_TRUE(graph->GetBlocks()[3]->IsLoopHeader()); |
| 314 | HLoopInformation* info = graph->GetBlocks()[3]->GetLoopInformation(); |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 315 | ASSERT_EQ(1u, info->NumberOfBackEdges()); |
| 316 | ASSERT_FALSE(info->GetHeader()->Dominates(info->GetBackEdges()[0])); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 317 | } |
| 318 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 319 | TEST_F(FindLoopsTest, DoWhileLoop) { |
Mathieu Chartier | fa3db3d | 2018-01-12 14:42:18 -0800 | [diff] [blame] | 320 | const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 321 | Instruction::CONST_4 | 0 | 0, |
| 322 | Instruction::GOTO | 0x0100, |
| 323 | Instruction::IF_EQ, 0xFFFF, |
| 324 | Instruction::RETURN | 0 << 8); |
| 325 | |
Vladimir Marko | ca6fff8 | 2017-10-03 14:49:14 +0100 | [diff] [blame] | 326 | HGraph* graph = CreateCFG(data); |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 327 | |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 328 | TestBlock(graph, 0, false, kInvalidBlockId); // entry block |
| 329 | TestBlock(graph, 1, false, kInvalidBlockId); // pre header of first loop |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 330 | const int blocks2[] = {2, 3, 6}; |
Vladimir Marko | fa6b93c | 2015-09-15 10:15:55 +0100 | [diff] [blame] | 331 | TestBlock(graph, 2, true, 2, blocks2, 3); // loop header |
| 332 | TestBlock(graph, 3, false, 2); // back edge of first loop |
| 333 | TestBlock(graph, 4, false, kInvalidBlockId); // return block |
| 334 | TestBlock(graph, 5, false, kInvalidBlockId); // exit block |
| 335 | TestBlock(graph, 6, false, 2); // synthesized block to avoid a critical edge |
Nicolas Geoffray | 622d9c3 | 2014-05-12 16:11:02 +0100 | [diff] [blame] | 336 | } |
| 337 | |
| 338 | } // namespace art |