1 /* 2 * Copyright (C) 2017 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 "graph_checker.h" 18 #include "nodes.h" 19 #include "optimizing_unit_test.h" 20 #include "superblock_cloner.h" 21 22 #include "gtest/gtest.h" 23 24 namespace art { 25 26 using HBasicBlockMap = SuperblockCloner::HBasicBlockMap; 27 using HInstructionMap = SuperblockCloner::HInstructionMap; 28 29 // This class provides methods and helpers for testing various cloning and copying routines: 30 // individual instruction cloning and cloning of the more coarse-grain structures. 31 class SuperblockClonerTest : public OptimizingUnitTest { 32 public: 33 SuperblockClonerTest() 34 : graph_(CreateGraph()), entry_block_(nullptr), exit_block_(nullptr), parameter_(nullptr) {} 35 36 void CreateBasicLoopControlFlow(/* out */ HBasicBlock** header_p, 37 /* out */ HBasicBlock** body_p) { 38 entry_block_ = new (GetAllocator()) HBasicBlock(graph_); 39 graph_->AddBlock(entry_block_); 40 graph_->SetEntryBlock(entry_block_); 41 42 HBasicBlock* loop_preheader = new (GetAllocator()) HBasicBlock(graph_); 43 HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_); 44 HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_); 45 HBasicBlock* loop_exit = new (GetAllocator()) HBasicBlock(graph_); 46 47 graph_->AddBlock(loop_preheader); 48 graph_->AddBlock(loop_header); 49 graph_->AddBlock(loop_body); 50 graph_->AddBlock(loop_exit); 51 52 exit_block_ = new (GetAllocator()) HBasicBlock(graph_); 53 graph_->AddBlock(exit_block_); 54 graph_->SetExitBlock(exit_block_); 55 56 entry_block_->AddSuccessor(loop_preheader); 57 loop_preheader->AddSuccessor(loop_header); 58 // Loop exit first to have a proper exit condition/target for HIf. 59 loop_header->AddSuccessor(loop_exit); 60 loop_header->AddSuccessor(loop_body); 61 loop_body->AddSuccessor(loop_header); 62 loop_exit->AddSuccessor(exit_block_); 63 64 *header_p = loop_header; 65 *body_p = loop_body; 66 67 parameter_ = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 68 dex::TypeIndex(0), 69 0, 70 DataType::Type::kInt32); 71 entry_block_->AddInstruction(parameter_); 72 loop_exit->AddInstruction(new (GetAllocator()) HReturnVoid()); 73 exit_block_->AddInstruction(new (GetAllocator()) HExit()); 74 } 75 76 void CreateBasicLoopDataFlow(HBasicBlock* loop_header, HBasicBlock* loop_body) { 77 uint32_t dex_pc = 0; 78 79 // Entry block. 80 HIntConstant* const_0 = graph_->GetIntConstant(0); 81 HIntConstant* const_1 = graph_->GetIntConstant(1); 82 HIntConstant* const_128 = graph_->GetIntConstant(128); 83 84 // Header block. 85 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32); 86 HInstruction* suspend_check = new (GetAllocator()) HSuspendCheck(); 87 88 loop_header->AddPhi(phi); 89 loop_header->AddInstruction(suspend_check); 90 loop_header->AddInstruction(new (GetAllocator()) HGreaterThanOrEqual(phi, const_128)); 91 loop_header->AddInstruction(new (GetAllocator()) HIf(parameter_)); 92 93 // Loop body block. 94 HInstruction* null_check = new (GetAllocator()) HNullCheck(parameter_, dex_pc); 95 HInstruction* array_length = new (GetAllocator()) HArrayLength(null_check, dex_pc); 96 HInstruction* bounds_check = new (GetAllocator()) HBoundsCheck(phi, array_length, dex_pc); 97 HInstruction* array_get = 98 new (GetAllocator()) HArrayGet(null_check, bounds_check, DataType::Type::kInt32, dex_pc); 99 HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, array_get, const_1); 100 HInstruction* array_set = 101 new (GetAllocator()) HArraySet(null_check, bounds_check, add, DataType::Type::kInt32, dex_pc); 102 HInstruction* induction_inc = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi, const_1); 103 104 loop_body->AddInstruction(null_check); 105 loop_body->AddInstruction(array_length); 106 loop_body->AddInstruction(bounds_check); 107 loop_body->AddInstruction(array_get); 108 loop_body->AddInstruction(add); 109 loop_body->AddInstruction(array_set); 110 loop_body->AddInstruction(induction_inc); 111 loop_body->AddInstruction(new (GetAllocator()) HGoto()); 112 113 phi->AddInput(const_0); 114 phi->AddInput(induction_inc); 115 116 graph_->SetHasBoundsChecks(true); 117 118 // Adjust HEnvironment for each instruction which require that. 119 ArenaVector<HInstruction*> current_locals({phi, const_128, parameter_}, 120 GetAllocator()->Adapter(kArenaAllocInstruction)); 121 122 HEnvironment* env = ManuallyBuildEnvFor(suspend_check, ¤t_locals); 123 null_check->CopyEnvironmentFrom(env); 124 bounds_check->CopyEnvironmentFrom(env); 125 } 126 127 HEnvironment* ManuallyBuildEnvFor(HInstruction* instruction, 128 ArenaVector<HInstruction*>* current_locals) { 129 HEnvironment* environment = new (GetAllocator()) HEnvironment( 130 (GetAllocator()), 131 current_locals->size(), 132 graph_->GetArtMethod(), 133 instruction->GetDexPc(), 134 instruction); 135 136 environment->CopyFrom(ArrayRef<HInstruction* const>(*current_locals)); 137 instruction->SetRawEnvironment(environment); 138 return environment; 139 } 140 141 bool CheckGraph() { 142 GraphChecker checker(graph_); 143 checker.Run(); 144 if (!checker.IsValid()) { 145 for (const std::string& error : checker.GetErrors()) { 146 std::cout << error << std::endl; 147 } 148 return false; 149 } 150 return true; 151 } 152 153 HGraph* graph_; 154 155 HBasicBlock* entry_block_; 156 HBasicBlock* exit_block_; 157 158 HInstruction* parameter_; 159 }; 160 161 TEST_F(SuperblockClonerTest, IndividualInstrCloner) { 162 HBasicBlock* header = nullptr; 163 HBasicBlock* loop_body = nullptr; 164 165 CreateBasicLoopControlFlow(&header, &loop_body); 166 CreateBasicLoopDataFlow(header, loop_body); 167 graph_->BuildDominatorTree(); 168 ASSERT_TRUE(CheckGraph()); 169 170 HSuspendCheck* old_suspend_check = header->GetLoopInformation()->GetSuspendCheck(); 171 CloneAndReplaceInstructionVisitor visitor(graph_); 172 // Do instruction cloning and replacement twice with different visiting order. 173 174 visitor.VisitInsertionOrder(); 175 size_t instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount(); 176 EXPECT_EQ(instr_replaced_by_clones_count, 12u); 177 EXPECT_TRUE(CheckGraph()); 178 179 visitor.VisitReversePostOrder(); 180 instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount(); 181 EXPECT_EQ(instr_replaced_by_clones_count, 24u); 182 EXPECT_TRUE(CheckGraph()); 183 184 HSuspendCheck* new_suspend_check = header->GetLoopInformation()->GetSuspendCheck(); 185 EXPECT_NE(new_suspend_check, old_suspend_check); 186 EXPECT_NE(new_suspend_check, nullptr); 187 } 188 189 // Tests SuperblockCloner::CloneBasicBlocks - check instruction cloning and initial remapping of 190 // instructions' inputs. 191 TEST_F(SuperblockClonerTest, CloneBasicBlocks) { 192 HBasicBlock* header = nullptr; 193 HBasicBlock* loop_body = nullptr; 194 ArenaAllocator* arena = graph_->GetAllocator(); 195 196 CreateBasicLoopControlFlow(&header, &loop_body); 197 CreateBasicLoopDataFlow(header, loop_body); 198 graph_->BuildDominatorTree(); 199 ASSERT_TRUE(CheckGraph()); 200 201 ArenaBitVector orig_bb_set( 202 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner); 203 HBasicBlockMap bb_map(std::less<HBasicBlock*>(), arena->Adapter(kArenaAllocSuperblockCloner)); 204 HInstructionMap hir_map(std::less<HInstruction*>(), arena->Adapter(kArenaAllocSuperblockCloner)); 205 206 HLoopInformation* loop_info = header->GetLoopInformation(); 207 orig_bb_set.Union(&loop_info->GetBlocks()); 208 209 SuperblockCloner cloner(graph_, 210 &orig_bb_set, 211 &bb_map, 212 &hir_map); 213 EXPECT_TRUE(cloner.IsSubgraphClonable()); 214 215 cloner.CloneBasicBlocks(); 216 217 EXPECT_EQ(bb_map.size(), 2u); 218 EXPECT_EQ(hir_map.size(), 12u); 219 220 for (auto it : hir_map) { 221 HInstruction* orig_instr = it.first; 222 HInstruction* copy_instr = it.second; 223 224 EXPECT_EQ(cloner.GetBlockCopy(orig_instr->GetBlock()), copy_instr->GetBlock()); 225 EXPECT_EQ(orig_instr->GetKind(), copy_instr->GetKind()); 226 EXPECT_EQ(orig_instr->GetType(), copy_instr->GetType()); 227 228 if (orig_instr->IsPhi()) { 229 continue; 230 } 231 232 EXPECT_EQ(orig_instr->InputCount(), copy_instr->InputCount()); 233 234 // Check that inputs match. 235 for (size_t i = 0, e = orig_instr->InputCount(); i < e; i++) { 236 HInstruction* orig_input = orig_instr->InputAt(i); 237 HInstruction* copy_input = copy_instr->InputAt(i); 238 if (cloner.IsInOrigBBSet(orig_input->GetBlock())) { 239 EXPECT_EQ(cloner.GetInstrCopy(orig_input), copy_input); 240 } else { 241 EXPECT_EQ(orig_input, copy_input); 242 } 243 } 244 245 EXPECT_EQ(orig_instr->HasEnvironment(), copy_instr->HasEnvironment()); 246 247 // Check that environments match. 248 if (orig_instr->HasEnvironment()) { 249 HEnvironment* orig_env = orig_instr->GetEnvironment(); 250 HEnvironment* copy_env = copy_instr->GetEnvironment(); 251 252 EXPECT_EQ(copy_env->GetParent(), nullptr); 253 EXPECT_EQ(orig_env->Size(), copy_env->Size()); 254 255 for (size_t i = 0, e = orig_env->Size(); i < e; i++) { 256 HInstruction* orig_input = orig_env->GetInstructionAt(i); 257 HInstruction* copy_input = copy_env->GetInstructionAt(i); 258 if (cloner.IsInOrigBBSet(orig_input->GetBlock())) { 259 EXPECT_EQ(cloner.GetInstrCopy(orig_input), copy_input); 260 } else { 261 EXPECT_EQ(orig_input, copy_input); 262 } 263 } 264 } 265 } 266 } 267 268 // SuperblockCloner::CleanUpControlFlow - checks algorithms of local adjustments of the control 269 // flow. 270 TEST_F(SuperblockClonerTest, AdjustControlFlowInfo) { 271 HBasicBlock* header = nullptr; 272 HBasicBlock* loop_body = nullptr; 273 ArenaAllocator* arena = graph_->GetAllocator(); 274 275 CreateBasicLoopControlFlow(&header, &loop_body); 276 CreateBasicLoopDataFlow(header, loop_body); 277 graph_->BuildDominatorTree(); 278 ASSERT_TRUE(CheckGraph()); 279 280 ArenaBitVector orig_bb_set( 281 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner); 282 283 HLoopInformation* loop_info = header->GetLoopInformation(); 284 orig_bb_set.Union(&loop_info->GetBlocks()); 285 286 SuperblockCloner cloner(graph_, 287 &orig_bb_set, 288 nullptr, 289 nullptr); 290 EXPECT_TRUE(cloner.IsSubgraphClonable()); 291 292 cloner.FindAndSetLocalAreaForAdjustments(); 293 cloner.CleanUpControlFlow(); 294 295 EXPECT_TRUE(CheckGraph()); 296 297 EXPECT_TRUE(entry_block_->Dominates(header)); 298 EXPECT_TRUE(entry_block_->Dominates(exit_block_)); 299 300 EXPECT_EQ(header->GetLoopInformation(), loop_info); 301 EXPECT_EQ(loop_info->GetHeader(), header); 302 EXPECT_TRUE(loop_info->Contains(*loop_body)); 303 EXPECT_TRUE(loop_info->IsBackEdge(*loop_body)); 304 } 305 306 } // namespace art 307