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 "base/arena_allocator.h" 18 #include "builder.h" 19 #include "dex/dex_instruction.h" 20 #include "nodes.h" 21 #include "optimizing_unit_test.h" 22 23 #include "gtest/gtest.h" 24 25 namespace art { 26 27 class OptimizerTest : public OptimizingUnitTest { 28 protected: 29 void TestCode(const std::vector<uint16_t>& data, const uint32_t* blocks, size_t blocks_length); 30 }; 31 32 void OptimizerTest::TestCode(const std::vector<uint16_t>& data, 33 const uint32_t* blocks, 34 size_t blocks_length) { 35 HGraph* graph = CreateCFG(data); 36 ASSERT_EQ(graph->GetBlocks().size(), blocks_length); 37 for (size_t i = 0, e = blocks_length; i < e; ++i) { 38 if (blocks[i] == kInvalidBlockId) { 39 if (graph->GetBlocks()[i] == nullptr) { 40 // Dead block. 41 } else { 42 // Only the entry block has no dominator. 43 ASSERT_EQ(nullptr, graph->GetBlocks()[i]->GetDominator()); 44 ASSERT_TRUE(graph->GetBlocks()[i]->IsEntryBlock()); 45 } 46 } else { 47 ASSERT_NE(nullptr, graph->GetBlocks()[i]->GetDominator()); 48 ASSERT_EQ(blocks[i], graph->GetBlocks()[i]->GetDominator()->GetBlockId()); 49 } 50 } 51 } 52 53 TEST_F(OptimizerTest, ReturnVoid) { 54 const std::vector<uint16_t> data = ZERO_REGISTER_CODE_ITEM( 55 Instruction::RETURN_VOID); // Block number 1 56 57 const uint32_t dominators[] = { 58 kInvalidBlockId, 59 0, 60 1 61 }; 62 63 TestCode(data, dominators, sizeof(dominators) / sizeof(int)); 64 } 65 66 TEST_F(OptimizerTest, CFG1) { 67 const std::vector<uint16_t> data = ZERO_REGISTER_CODE_ITEM( 68 Instruction::GOTO | 0x100, // Block number 1 69 Instruction::RETURN_VOID); // Block number 2 70 71 const uint32_t dominators[] = { 72 kInvalidBlockId, 73 0, 74 1, 75 2 76 }; 77 78 TestCode(data, dominators, sizeof(dominators) / sizeof(int)); 79 } 80 81 TEST_F(OptimizerTest, CFG2) { 82 const std::vector<uint16_t> data = ZERO_REGISTER_CODE_ITEM( 83 Instruction::GOTO | 0x100, // Block number 1 84 Instruction::GOTO | 0x100, // Block number 2 85 Instruction::RETURN_VOID); // Block number 3 86 87 const uint32_t dominators[] = { 88 kInvalidBlockId, 89 0, 90 1, 91 2, 92 3 93 }; 94 95 TestCode(data, dominators, sizeof(dominators) / sizeof(int)); 96 } 97 98 TEST_F(OptimizerTest, CFG3) { 99 const std::vector<uint16_t> data1 = ZERO_REGISTER_CODE_ITEM( 100 Instruction::GOTO | 0x200, // Block number 1 101 Instruction::RETURN_VOID, // Block number 2 102 Instruction::GOTO | 0xFF00); // Block number 3 103 104 const uint32_t dominators[] = { 105 kInvalidBlockId, 106 0, 107 3, 108 1, 109 2 110 }; 111 112 TestCode(data1, dominators, sizeof(dominators) / sizeof(int)); 113 114 const std::vector<uint16_t> data2 = ZERO_REGISTER_CODE_ITEM( 115 Instruction::GOTO_16, 3, 116 Instruction::RETURN_VOID, 117 Instruction::GOTO_16, 0xFFFF); 118 119 TestCode(data2, dominators, sizeof(dominators) / sizeof(int)); 120 121 const std::vector<uint16_t> data3 = ZERO_REGISTER_CODE_ITEM( 122 Instruction::GOTO_32, 4, 0, 123 Instruction::RETURN_VOID, 124 Instruction::GOTO_32, 0xFFFF, 0xFFFF); 125 126 TestCode(data3, dominators, sizeof(dominators) / sizeof(int)); 127 } 128 129 TEST_F(OptimizerTest, CFG4) { 130 const std::vector<uint16_t> data1 = ZERO_REGISTER_CODE_ITEM( 131 Instruction::NOP, 132 Instruction::GOTO | 0xFF00); 133 134 const uint32_t dominators[] = { 135 kInvalidBlockId, 136 3, 137 kInvalidBlockId, 138 0 139 }; 140 141 TestCode(data1, dominators, sizeof(dominators) / sizeof(int)); 142 143 const std::vector<uint16_t> data2 = ZERO_REGISTER_CODE_ITEM( 144 Instruction::GOTO_32, 0, 0); 145 146 TestCode(data2, dominators, sizeof(dominators) / sizeof(int)); 147 } 148 149 TEST_F(OptimizerTest, CFG5) { 150 const std::vector<uint16_t> data = ZERO_REGISTER_CODE_ITEM( 151 Instruction::RETURN_VOID, // Block number 1 152 Instruction::GOTO | 0x100, // Dead block 153 Instruction::GOTO | 0xFE00); // Block number 2 154 155 156 const uint32_t dominators[] = { 157 kInvalidBlockId, 158 0, 159 kInvalidBlockId, 160 1 161 }; 162 163 TestCode(data, dominators, sizeof(dominators) / sizeof(int)); 164 } 165 166 TEST_F(OptimizerTest, CFG6) { 167 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 168 Instruction::CONST_4 | 0 | 0, 169 Instruction::IF_EQ, 3, 170 Instruction::GOTO | 0x100, 171 Instruction::RETURN_VOID); 172 173 const uint32_t dominators[] = { 174 kInvalidBlockId, 175 0, 176 1, 177 1, 178 3, 179 1, // Synthesized block to avoid critical edge. 180 }; 181 182 TestCode(data, dominators, sizeof(dominators) / sizeof(int)); 183 } 184 185 TEST_F(OptimizerTest, CFG7) { 186 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 187 Instruction::CONST_4 | 0 | 0, 188 Instruction::IF_EQ, 3, // Block number 1 189 Instruction::GOTO | 0x100, // Block number 2 190 Instruction::GOTO | 0xFF00); // Block number 3 191 192 const uint32_t dominators[] = { 193 kInvalidBlockId, 194 0, 195 1, 196 1, 197 kInvalidBlockId, // exit block is not dominated by any block due to the spin loop. 198 1, // block to avoid critical edge. 199 1 // block to avoid critical edge. 200 }; 201 202 TestCode(data, dominators, sizeof(dominators) / sizeof(int)); 203 } 204 205 TEST_F(OptimizerTest, CFG8) { 206 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 207 Instruction::CONST_4 | 0 | 0, 208 Instruction::IF_EQ, 3, // Block number 1 209 Instruction::GOTO | 0x200, // Block number 2 210 Instruction::GOTO | 0x100, // Block number 3 211 Instruction::GOTO | 0xFF00); // Block number 4 212 213 const uint32_t dominators[] = { 214 kInvalidBlockId, 215 0, 216 1, 217 1, 218 1, 219 kInvalidBlockId, // exit block is not dominated by any block due to the spin loop. 220 1 // block to avoid critical edge. 221 }; 222 223 TestCode(data, dominators, sizeof(dominators) / sizeof(int)); 224 } 225 226 TEST_F(OptimizerTest, CFG9) { 227 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 228 Instruction::CONST_4 | 0 | 0, 229 Instruction::IF_EQ, 3, // Block number 1 230 Instruction::GOTO | 0x200, // Block number 2 231 Instruction::GOTO | 0x100, // Block number 3 232 Instruction::GOTO | 0xFE00); // Block number 4 233 234 const uint32_t dominators[] = { 235 kInvalidBlockId, 236 0, 237 1, 238 1, 239 1, 240 kInvalidBlockId, // exit block is not dominated by any block due to the spin loop. 241 1 // block to avoid critical edge. 242 }; 243 244 TestCode(data, dominators, sizeof(dominators) / sizeof(int)); 245 } 246 247 TEST_F(OptimizerTest, CFG10) { 248 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM( 249 Instruction::CONST_4 | 0 | 0, 250 Instruction::IF_EQ, 6, // Block number 1 251 Instruction::IF_EQ, 3, // Block number 2 252 Instruction::GOTO | 0x100, // Block number 3 253 Instruction::GOTO | 0x100, // Block number 4 254 Instruction::RETURN_VOID); // Block number 5 255 256 const uint32_t dominators[] = { 257 kInvalidBlockId, 258 0, 259 1, 260 2, 261 2, 262 1, 263 5, // Block number 5 dominates exit block 264 1, // block to avoid critical edge. 265 2 // block to avoid critical edge. 266 }; 267 268 TestCode(data, dominators, sizeof(dominators) / sizeof(int)); 269 } 270 271 } // namespace art 272
