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