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