1 /* 2 * Copyright (C) 2015 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 <regex> 18 19 #include "base/arena_allocator.h" 20 #include "builder.h" 21 #include "induction_var_analysis.h" 22 #include "nodes.h" 23 #include "optimizing_unit_test.h" 24 25 namespace art { 26 27 /** 28 * Fixture class for the InductionVarAnalysis tests. 29 */ 30 class InductionVarAnalysisTest : public CommonCompilerTest { 31 public: 32 InductionVarAnalysisTest() : pool_(), allocator_(&pool_) { 33 graph_ = CreateGraph(&allocator_); 34 } 35 36 ~InductionVarAnalysisTest() { } 37 38 // Builds single for-loop at depth d. 39 void BuildForLoop(int d, int n) { 40 ASSERT_LT(d, n); 41 loop_preheader_[d] = new (&allocator_) HBasicBlock(graph_); 42 graph_->AddBlock(loop_preheader_[d]); 43 loop_header_[d] = new (&allocator_) HBasicBlock(graph_); 44 graph_->AddBlock(loop_header_[d]); 45 loop_preheader_[d]->AddSuccessor(loop_header_[d]); 46 if (d < (n - 1)) { 47 BuildForLoop(d + 1, n); 48 } 49 loop_body_[d] = new (&allocator_) HBasicBlock(graph_); 50 graph_->AddBlock(loop_body_[d]); 51 loop_body_[d]->AddSuccessor(loop_header_[d]); 52 if (d < (n - 1)) { 53 loop_header_[d]->AddSuccessor(loop_preheader_[d + 1]); 54 loop_header_[d + 1]->AddSuccessor(loop_body_[d]); 55 } else { 56 loop_header_[d]->AddSuccessor(loop_body_[d]); 57 } 58 } 59 60 // Builds a n-nested loop in CFG where each loop at depth 0 <= d < n 61 // is defined as "for (int i_d = 0; i_d < 100; i_d++)". Tests can further 62 // populate the loop with instructions to set up interesting scenarios. 63 void BuildLoopNest(int n) { 64 ASSERT_LE(n, 10); 65 graph_->SetNumberOfVRegs(n + 3); 66 67 // Build basic blocks with entry, nested loop, exit. 68 entry_ = new (&allocator_) HBasicBlock(graph_); 69 graph_->AddBlock(entry_); 70 BuildForLoop(0, n); 71 return_ = new (&allocator_) HBasicBlock(graph_); 72 graph_->AddBlock(return_); 73 exit_ = new (&allocator_) HBasicBlock(graph_); 74 graph_->AddBlock(exit_); 75 entry_->AddSuccessor(loop_preheader_[0]); 76 loop_header_[0]->AddSuccessor(return_); 77 return_->AddSuccessor(exit_); 78 graph_->SetEntryBlock(entry_); 79 graph_->SetExitBlock(exit_); 80 81 // Provide entry and exit instructions. 82 parameter_ = new (&allocator_) HParameterValue( 83 graph_->GetDexFile(), 0, 0, Primitive::kPrimNot, true); 84 entry_->AddInstruction(parameter_); 85 constant0_ = graph_->GetIntConstant(0); 86 constant1_ = graph_->GetIntConstant(1); 87 constant100_ = graph_->GetIntConstant(100); 88 float_constant0_ = graph_->GetFloatConstant(0.0f); 89 return_->AddInstruction(new (&allocator_) HReturnVoid()); 90 exit_->AddInstruction(new (&allocator_) HExit()); 91 92 // Provide loop instructions. 93 for (int d = 0; d < n; d++) { 94 basic_[d] = new (&allocator_) HPhi(&allocator_, d, 0, Primitive::kPrimInt); 95 loop_preheader_[d]->AddInstruction(new (&allocator_) HGoto()); 96 loop_header_[d]->AddPhi(basic_[d]); 97 HInstruction* compare = new (&allocator_) HLessThan(basic_[d], constant100_); 98 loop_header_[d]->AddInstruction(compare); 99 loop_header_[d]->AddInstruction(new (&allocator_) HIf(compare)); 100 increment_[d] = new (&allocator_) HAdd(Primitive::kPrimInt, basic_[d], constant1_); 101 loop_body_[d]->AddInstruction(increment_[d]); 102 loop_body_[d]->AddInstruction(new (&allocator_) HGoto()); 103 104 basic_[d]->AddInput(constant0_); 105 basic_[d]->AddInput(increment_[d]); 106 } 107 } 108 109 // Builds if-statement at depth d. 110 HPhi* BuildIf(int d, HBasicBlock** ifT, HBasicBlock **ifF) { 111 HBasicBlock* cond = new (&allocator_) HBasicBlock(graph_); 112 HBasicBlock* ifTrue = new (&allocator_) HBasicBlock(graph_); 113 HBasicBlock* ifFalse = new (&allocator_) HBasicBlock(graph_); 114 graph_->AddBlock(cond); 115 graph_->AddBlock(ifTrue); 116 graph_->AddBlock(ifFalse); 117 // Conditional split. 118 loop_header_[d]->ReplaceSuccessor(loop_body_[d], cond); 119 cond->AddSuccessor(ifTrue); 120 cond->AddSuccessor(ifFalse); 121 ifTrue->AddSuccessor(loop_body_[d]); 122 ifFalse->AddSuccessor(loop_body_[d]); 123 cond->AddInstruction(new (&allocator_) HIf(parameter_)); 124 *ifT = ifTrue; 125 *ifF = ifFalse; 126 127 HPhi* select_phi = new (&allocator_) HPhi(&allocator_, -1, 0, Primitive::kPrimInt); 128 loop_body_[d]->AddPhi(select_phi); 129 return select_phi; 130 } 131 132 // Inserts instruction right before increment at depth d. 133 HInstruction* InsertInstruction(HInstruction* instruction, int d) { 134 loop_body_[d]->InsertInstructionBefore(instruction, increment_[d]); 135 return instruction; 136 } 137 138 // Inserts a phi to loop header at depth d and returns it. 139 HPhi* InsertLoopPhi(int vreg, int d) { 140 HPhi* phi = new (&allocator_) HPhi(&allocator_, vreg, 0, Primitive::kPrimInt); 141 loop_header_[d]->AddPhi(phi); 142 return phi; 143 } 144 145 // Inserts an array store with given `subscript` at depth d to 146 // enable tests to inspect the computed induction at that point easily. 147 HInstruction* InsertArrayStore(HInstruction* subscript, int d) { 148 // ArraySet is given a float value in order to avoid SsaBuilder typing 149 // it from the array's non-existent reference type info. 150 return InsertInstruction(new (&allocator_) HArraySet( 151 parameter_, subscript, float_constant0_, Primitive::kPrimFloat, 0), d); 152 } 153 154 // Returns induction information of instruction in loop at depth d. 155 std::string GetInductionInfo(HInstruction* instruction, int d) { 156 return HInductionVarAnalysis::InductionToString( 157 iva_->LookupInfo(loop_body_[d]->GetLoopInformation(), instruction)); 158 } 159 160 // Returns true if instructions have identical induction. 161 bool HaveSameInduction(HInstruction* instruction1, HInstruction* instruction2) { 162 return HInductionVarAnalysis::InductionEqual( 163 iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction1), 164 iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction2)); 165 } 166 167 // Performs InductionVarAnalysis (after proper set up). 168 void PerformInductionVarAnalysis() { 169 graph_->BuildDominatorTree(); 170 iva_ = new (&allocator_) HInductionVarAnalysis(graph_); 171 iva_->Run(); 172 } 173 174 // General building fields. 175 ArenaPool pool_; 176 ArenaAllocator allocator_; 177 HGraph* graph_; 178 HInductionVarAnalysis* iva_; 179 180 // Fixed basic blocks and instructions. 181 HBasicBlock* entry_; 182 HBasicBlock* return_; 183 HBasicBlock* exit_; 184 HInstruction* parameter_; // "this" 185 HInstruction* constant0_; 186 HInstruction* constant1_; 187 HInstruction* constant100_; 188 HInstruction* float_constant0_; 189 190 // Loop specifics. 191 HBasicBlock* loop_preheader_[10]; 192 HBasicBlock* loop_header_[10]; 193 HBasicBlock* loop_body_[10]; 194 HInstruction* increment_[10]; 195 HPhi* basic_[10]; // "vreg_d", the "i_d" 196 }; 197 198 // 199 // The actual InductionVarAnalysis tests. 200 // 201 202 TEST_F(InductionVarAnalysisTest, ProperLoopSetup) { 203 // Setup: 204 // for (int i_0 = 0; i_0 < 100; i_0++) { 205 // .. 206 // for (int i_9 = 0; i_9 < 100; i_9++) { 207 // } 208 // .. 209 // } 210 BuildLoopNest(10); 211 graph_->BuildDominatorTree(); 212 213 ASSERT_EQ(entry_->GetLoopInformation(), nullptr); 214 for (int d = 0; d < 1; d++) { 215 ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(), 216 (d == 0) ? nullptr 217 : loop_header_[d - 1]->GetLoopInformation()); 218 ASSERT_NE(loop_header_[d]->GetLoopInformation(), nullptr); 219 ASSERT_NE(loop_body_[d]->GetLoopInformation(), nullptr); 220 ASSERT_EQ(loop_header_[d]->GetLoopInformation(), 221 loop_body_[d]->GetLoopInformation()); 222 } 223 ASSERT_EQ(exit_->GetLoopInformation(), nullptr); 224 } 225 226 TEST_F(InductionVarAnalysisTest, FindBasicInduction) { 227 // Setup: 228 // for (int i = 0; i < 100; i++) { 229 // a[i] = 0; 230 // } 231 BuildLoopNest(1); 232 HInstruction* store = InsertArrayStore(basic_[0], 0); 233 PerformInductionVarAnalysis(); 234 235 EXPECT_STREQ("((1) * i + (0)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str()); 236 EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(increment_[0], 0).c_str()); 237 238 // Offset matters! 239 EXPECT_FALSE(HaveSameInduction(store->InputAt(1), increment_[0])); 240 241 // Trip-count. 242 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", 243 GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 244 } 245 246 TEST_F(InductionVarAnalysisTest, FindDerivedInduction) { 247 // Setup: 248 // for (int i = 0; i < 100; i++) { 249 // k = 100 + i; 250 // k = 100 - i; 251 // k = 100 * i; 252 // k = i << 1; 253 // k = - i; 254 // } 255 BuildLoopNest(1); 256 HInstruction *add = InsertInstruction( 257 new (&allocator_) HAdd(Primitive::kPrimInt, constant100_, basic_[0]), 0); 258 HInstruction *sub = InsertInstruction( 259 new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0); 260 HInstruction *mul = InsertInstruction( 261 new (&allocator_) HMul(Primitive::kPrimInt, constant100_, basic_[0]), 0); 262 HInstruction *shl = InsertInstruction( 263 new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0); 264 HInstruction *neg = InsertInstruction( 265 new (&allocator_) HNeg(Primitive::kPrimInt, basic_[0]), 0); 266 PerformInductionVarAnalysis(); 267 268 EXPECT_STREQ("((1) * i + (100)):PrimInt", GetInductionInfo(add, 0).c_str()); 269 EXPECT_STREQ("(( - (1)) * i + (100)):PrimInt", GetInductionInfo(sub, 0).c_str()); 270 EXPECT_STREQ("((100) * i + (0)):PrimInt", GetInductionInfo(mul, 0).c_str()); 271 EXPECT_STREQ("((2) * i + (0)):PrimInt", GetInductionInfo(shl, 0).c_str()); 272 EXPECT_STREQ("(( - (1)) * i + (0)):PrimInt", GetInductionInfo(neg, 0).c_str()); 273 } 274 275 TEST_F(InductionVarAnalysisTest, FindChainInduction) { 276 // Setup: 277 // k = 0; 278 // for (int i = 0; i < 100; i++) { 279 // k = k + 100; 280 // a[k] = 0; 281 // k = k - 1; 282 // a[k] = 0; 283 // } 284 BuildLoopNest(1); 285 HPhi* k = InsertLoopPhi(0, 0); 286 k->AddInput(constant0_); 287 288 HInstruction *add = InsertInstruction( 289 new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0); 290 HInstruction* store1 = InsertArrayStore(add, 0); 291 HInstruction *sub = InsertInstruction( 292 new (&allocator_) HSub(Primitive::kPrimInt, add, constant1_), 0); 293 HInstruction* store2 = InsertArrayStore(sub, 0); 294 k->AddInput(sub); 295 PerformInductionVarAnalysis(); 296 297 EXPECT_STREQ("(((100) - (1)) * i + (100)):PrimInt", 298 GetInductionInfo(store1->InputAt(1), 0).c_str()); 299 EXPECT_STREQ("(((100) - (1)) * i + ((100) - (1))):PrimInt", 300 GetInductionInfo(store2->InputAt(1), 0).c_str()); 301 } 302 303 TEST_F(InductionVarAnalysisTest, FindTwoWayBasicInduction) { 304 // Setup: 305 // k = 0; 306 // for (int i = 0; i < 100; i++) { 307 // if () k = k + 1; 308 // else k = k + 1; 309 // a[k] = 0; 310 // } 311 BuildLoopNest(1); 312 HPhi* k_header = InsertLoopPhi(0, 0); 313 k_header->AddInput(constant0_); 314 315 HBasicBlock* ifTrue; 316 HBasicBlock* ifFalse; 317 HPhi* k_body = BuildIf(0, &ifTrue, &ifFalse); 318 319 // True-branch. 320 HInstruction* inc1 = new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant1_); 321 ifTrue->AddInstruction(inc1); 322 k_body->AddInput(inc1); 323 // False-branch. 324 HInstruction* inc2 = new (&allocator_) HAdd(Primitive::kPrimInt, k_header, constant1_); 325 ifFalse->AddInstruction(inc2); 326 k_body->AddInput(inc2); 327 // Merge over a phi. 328 HInstruction* store = InsertArrayStore(k_body, 0); 329 k_header->AddInput(k_body); 330 PerformInductionVarAnalysis(); 331 332 EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str()); 333 334 // Both increments get same induction. 335 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc1)); 336 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc2)); 337 } 338 339 TEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) { 340 // Setup: 341 // for (int i = 0; i < 100; i++) { 342 // if () k = i + 1; 343 // else k = i + 1; 344 // a[k] = 0; 345 // } 346 BuildLoopNest(1); 347 HBasicBlock* ifTrue; 348 HBasicBlock* ifFalse; 349 HPhi* k = BuildIf(0, &ifTrue, &ifFalse); 350 351 // True-branch. 352 HInstruction* inc1 = new (&allocator_) HAdd(Primitive::kPrimInt, basic_[0], constant1_); 353 ifTrue->AddInstruction(inc1); 354 k->AddInput(inc1); 355 // False-branch. 356 HInstruction* inc2 = new (&allocator_) HAdd(Primitive::kPrimInt, basic_[0], constant1_); 357 ifFalse->AddInstruction(inc2); 358 k->AddInput(inc2); 359 // Merge over a phi. 360 HInstruction* store = InsertArrayStore(k, 0); 361 PerformInductionVarAnalysis(); 362 363 EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str()); 364 } 365 366 TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) { 367 // Setup: 368 // k = 0; 369 // for (int i = 0; i < 100; i++) { 370 // a[k] = 0; 371 // k = 100 - i; 372 // } 373 BuildLoopNest(1); 374 HPhi* k = InsertLoopPhi(0, 0); 375 k->AddInput(constant0_); 376 377 HInstruction* store = InsertArrayStore(k, 0); 378 HInstruction *sub = InsertInstruction( 379 new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0]), 0); 380 k->AddInput(sub); 381 PerformInductionVarAnalysis(); 382 383 EXPECT_STREQ("wrap((0), (( - (1)) * i + (100)):PrimInt):PrimInt", 384 GetInductionInfo(store->InputAt(1), 0).c_str()); 385 } 386 387 TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) { 388 // Setup: 389 // k = 0; 390 // t = 100; 391 // for (int i = 0; i < 100; i++) { 392 // a[k] = 0; 393 // k = t; 394 // t = 100 - i; 395 // } 396 BuildLoopNest(1); 397 HPhi* k = InsertLoopPhi(0, 0); 398 k->AddInput(constant0_); 399 HPhi* t = InsertLoopPhi(1, 0); 400 t->AddInput(constant100_); 401 402 HInstruction* store = InsertArrayStore(k, 0); 403 k->AddInput(t); 404 HInstruction *sub = InsertInstruction( 405 new (&allocator_) HSub(Primitive::kPrimInt, constant100_, basic_[0], 0), 0); 406 t->AddInput(sub); 407 PerformInductionVarAnalysis(); 408 409 EXPECT_STREQ("wrap((0), wrap((100), (( - (1)) * i + (100)):PrimInt):PrimInt):PrimInt", 410 GetInductionInfo(store->InputAt(1), 0).c_str()); 411 } 412 413 TEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) { 414 // Setup: 415 // k = 0; 416 // for (int i = 0; i < 100; i++) { 417 // t = k + 100; 418 // t = k - 100; 419 // t = k * 100; 420 // t = k << 1; 421 // t = - k; 422 // k = i << 1; 423 // } 424 BuildLoopNest(1); 425 HPhi* k = InsertLoopPhi(0, 0); 426 k->AddInput(constant0_); 427 428 HInstruction *add = InsertInstruction( 429 new (&allocator_) HAdd(Primitive::kPrimInt, k, constant100_), 0); 430 HInstruction *sub = InsertInstruction( 431 new (&allocator_) HSub(Primitive::kPrimInt, k, constant100_), 0); 432 HInstruction *mul = InsertInstruction( 433 new (&allocator_) HMul(Primitive::kPrimInt, k, constant100_), 0); 434 HInstruction *shl = InsertInstruction( 435 new (&allocator_) HShl(Primitive::kPrimInt, k, constant1_), 0); 436 HInstruction *neg = InsertInstruction( 437 new (&allocator_) HNeg(Primitive::kPrimInt, k), 0); 438 k->AddInput( 439 InsertInstruction(new (&allocator_) HShl(Primitive::kPrimInt, basic_[0], constant1_), 0)); 440 PerformInductionVarAnalysis(); 441 442 EXPECT_STREQ("wrap((100), ((2) * i + (100)):PrimInt):PrimInt", 443 GetInductionInfo(add, 0).c_str()); 444 EXPECT_STREQ("wrap(((0) - (100)), ((2) * i + ((0) - (100))):PrimInt):PrimInt", 445 GetInductionInfo(sub, 0).c_str()); 446 EXPECT_STREQ("wrap((0), (((2) * (100)) * i + (0)):PrimInt):PrimInt", 447 GetInductionInfo(mul, 0).c_str()); 448 EXPECT_STREQ("wrap((0), (((2) * (2)) * i + (0)):PrimInt):PrimInt", 449 GetInductionInfo(shl, 0).c_str()); 450 EXPECT_STREQ("wrap((0), (( - (2)) * i + (0)):PrimInt):PrimInt", 451 GetInductionInfo(neg, 0).c_str()); 452 } 453 454 TEST_F(InductionVarAnalysisTest, FindPeriodicInduction) { 455 // Setup: 456 // k = 0; 457 // t = 100; 458 // for (int i = 0; i < 100; i++) { 459 // a[k] = 0; 460 // a[t] = 0; 461 // // Swap t <-> k. 462 // d = t; 463 // t = k; 464 // k = d; 465 // } 466 BuildLoopNest(1); 467 HPhi* k = InsertLoopPhi(0, 0); 468 k->AddInput(constant0_); 469 HPhi* t = InsertLoopPhi(1, 0); 470 t->AddInput(constant100_); 471 472 HInstruction* store1 = InsertArrayStore(k, 0); 473 HInstruction* store2 = InsertArrayStore(t, 0); 474 k->AddInput(t); 475 t->AddInput(k); 476 PerformInductionVarAnalysis(); 477 478 EXPECT_STREQ("periodic((0), (100)):PrimInt", GetInductionInfo(store1->InputAt(1), 0).c_str()); 479 EXPECT_STREQ("periodic((100), (0)):PrimInt", GetInductionInfo(store2->InputAt(1), 0).c_str()); 480 } 481 482 TEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) { 483 // Setup: 484 // k = 0; 485 // for (int i = 0; i < 100; i++) { 486 // a[k] = 0; 487 // k = 1 - k; 488 // } 489 BuildLoopNest(1); 490 HPhi* k = InsertLoopPhi(0, 0); 491 k->AddInput(constant0_); 492 493 HInstruction* store = InsertArrayStore(k, 0); 494 HInstruction *sub = InsertInstruction( 495 new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k), 0); 496 k->AddInput(sub); 497 PerformInductionVarAnalysis(); 498 499 EXPECT_STREQ("periodic((0), (1)):PrimInt", GetInductionInfo(store->InputAt(1), 0).c_str()); 500 EXPECT_STREQ("periodic((1), (0)):PrimInt", GetInductionInfo(sub, 0).c_str()); 501 } 502 503 TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) { 504 // Setup: 505 // k = 0; 506 // for (int i = 0; i < 100; i++) { 507 // k = 1 - k; 508 // t = k + 100; 509 // t = k - 100; 510 // t = k * 100; 511 // t = k << 1; 512 // t = - k; 513 // } 514 BuildLoopNest(1); 515 HPhi* k_header = InsertLoopPhi(0, 0); 516 k_header->AddInput(constant0_); 517 518 HInstruction* k_body = InsertInstruction( 519 new (&allocator_) HSub(Primitive::kPrimInt, constant1_, k_header), 0); 520 k_header->AddInput(k_body); 521 522 // Derived expressions. 523 HInstruction *add = InsertInstruction( 524 new (&allocator_) HAdd(Primitive::kPrimInt, k_body, constant100_), 0); 525 HInstruction *sub = InsertInstruction( 526 new (&allocator_) HSub(Primitive::kPrimInt, k_body, constant100_), 0); 527 HInstruction *mul = InsertInstruction( 528 new (&allocator_) HMul(Primitive::kPrimInt, k_body, constant100_), 0); 529 HInstruction *shl = InsertInstruction( 530 new (&allocator_) HShl(Primitive::kPrimInt, k_body, constant1_), 0); 531 HInstruction *neg = InsertInstruction( 532 new (&allocator_) HNeg(Primitive::kPrimInt, k_body), 0); 533 PerformInductionVarAnalysis(); 534 535 EXPECT_STREQ("periodic(((1) + (100)), (100)):PrimInt", GetInductionInfo(add, 0).c_str()); 536 EXPECT_STREQ("periodic(((1) - (100)), ((0) - (100))):PrimInt", GetInductionInfo(sub, 0).c_str()); 537 EXPECT_STREQ("periodic((100), (0)):PrimInt", GetInductionInfo(mul, 0).c_str()); 538 EXPECT_STREQ("periodic((2), (0)):PrimInt", GetInductionInfo(shl, 0).c_str()); 539 EXPECT_STREQ("periodic(( - (1)), (0)):PrimInt", GetInductionInfo(neg, 0).c_str()); 540 } 541 542 TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) { 543 // Setup: 544 // k = 0; 545 // for (int i_0 = 0; i_0 < 100; i_0++) { 546 // .. 547 // for (int i_9 = 0; i_9 < 100; i_9++) { 548 // k = 1 + k; 549 // a[k] = 0; 550 // } 551 // .. 552 // } 553 BuildLoopNest(10); 554 555 HPhi* k[10]; 556 for (int d = 0; d < 10; d++) { 557 k[d] = InsertLoopPhi(0, d); 558 } 559 560 HInstruction *inc = InsertInstruction( 561 new (&allocator_) HAdd(Primitive::kPrimInt, constant1_, k[9]), 9); 562 HInstruction* store = InsertArrayStore(inc, 9); 563 564 for (int d = 0; d < 10; d++) { 565 k[d]->AddInput((d != 0) ? k[d - 1] : constant0_); 566 k[d]->AddInput((d != 9) ? k[d + 1] : inc); 567 } 568 PerformInductionVarAnalysis(); 569 570 // Avoid exact phi number, since that depends on the SSA building phase. 571 std::regex r("\\(\\(1\\) \\* i \\+ " 572 "\\(\\(1\\) \\+ \\(\\d+:Phi\\)\\)\\):PrimInt"); 573 574 for (int d = 0; d < 10; d++) { 575 if (d == 9) { 576 EXPECT_TRUE(std::regex_match(GetInductionInfo(store->InputAt(1), d), r)); 577 } else { 578 EXPECT_STREQ("", GetInductionInfo(store->InputAt(1), d).c_str()); 579 } 580 EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(increment_[d], d).c_str()); 581 // Trip-count. 582 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", 583 GetInductionInfo(loop_header_[d]->GetLastInstruction(), d).c_str()); 584 } 585 } 586 587 TEST_F(InductionVarAnalysisTest, ByteInductionIntLoopControl) { 588 // Setup: 589 // for (int i = 0; i < 100; i++) { 590 // k = (byte) i; 591 // a[k] = 0; 592 // a[i] = 0; 593 // } 594 BuildLoopNest(1); 595 HInstruction *conv = InsertInstruction( 596 new (&allocator_) HTypeConversion(Primitive::kPrimByte, basic_[0], -1), 0); 597 HInstruction* store1 = InsertArrayStore(conv, 0); 598 HInstruction* store2 = InsertArrayStore(basic_[0], 0); 599 PerformInductionVarAnalysis(); 600 601 // Regular int induction (i) is "transferred" over conversion into byte induction (k). 602 EXPECT_STREQ("((1) * i + (0)):PrimByte", GetInductionInfo(store1->InputAt(1), 0).c_str()); 603 EXPECT_STREQ("((1) * i + (0)):PrimInt", GetInductionInfo(store2->InputAt(1), 0).c_str()); 604 EXPECT_STREQ("((1) * i + (1)):PrimInt", GetInductionInfo(increment_[0], 0).c_str()); 605 606 // Type matters! 607 EXPECT_FALSE(HaveSameInduction(store1->InputAt(1), store2->InputAt(1))); 608 609 // Trip-count. 610 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", 611 GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 612 } 613 614 TEST_F(InductionVarAnalysisTest, ByteLoopControl1) { 615 // Setup: 616 // for (byte i = -128; i < 127; i++) { // just fits! 617 // } 618 BuildLoopNest(1); 619 basic_[0]->ReplaceInput(graph_->GetIntConstant(-128), 0); 620 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 621 ifs->ReplaceInput(graph_->GetIntConstant(127), 1); 622 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimByte, increment_[0], -1); 623 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 624 basic_[0]->ReplaceInput(conv, 1); 625 PerformInductionVarAnalysis(); 626 627 EXPECT_STREQ("((1) * i + ((-128) + (1))):PrimByte", GetInductionInfo(increment_[0], 0).c_str()); 628 // Trip-count. 629 EXPECT_STREQ("(((127) - (-128)) (TC-loop) ((-128) < (127)))", 630 GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 631 } 632 633 TEST_F(InductionVarAnalysisTest, ByteLoopControl2) { 634 // Setup: 635 // for (byte i = -128; i < 128; i++) { // infinite loop! 636 // } 637 BuildLoopNest(1); 638 basic_[0]->ReplaceInput(graph_->GetIntConstant(-128), 0); 639 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 640 ifs->ReplaceInput(graph_->GetIntConstant(128), 1); 641 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimByte, increment_[0], -1); 642 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 643 basic_[0]->ReplaceInput(conv, 1); 644 PerformInductionVarAnalysis(); 645 646 EXPECT_STREQ("((1) * i + ((-128) + (1))):PrimByte", GetInductionInfo(increment_[0], 0).c_str()); 647 // Trip-count undefined. 648 EXPECT_STREQ("", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 649 } 650 651 TEST_F(InductionVarAnalysisTest, ShortLoopControl1) { 652 // Setup: 653 // for (short i = -32768; i < 32767; i++) { // just fits! 654 // } 655 BuildLoopNest(1); 656 basic_[0]->ReplaceInput(graph_->GetIntConstant(-32768), 0); 657 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 658 ifs->ReplaceInput(graph_->GetIntConstant(32767), 1); 659 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimShort, increment_[0], -1); 660 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 661 basic_[0]->ReplaceInput(conv, 1); 662 PerformInductionVarAnalysis(); 663 664 EXPECT_STREQ("((1) * i + ((-32768) + (1))):PrimShort", 665 GetInductionInfo(increment_[0], 0).c_str()); 666 // Trip-count. 667 EXPECT_STREQ("(((32767) - (-32768)) (TC-loop) ((-32768) < (32767)))", 668 GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 669 } 670 671 TEST_F(InductionVarAnalysisTest, ShortLoopControl2) { 672 // Setup: 673 // for (short i = -32768; i < 32768; i++) { // infinite loop! 674 // } 675 BuildLoopNest(1); 676 basic_[0]->ReplaceInput(graph_->GetIntConstant(-32768), 0); 677 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 678 ifs->ReplaceInput(graph_->GetIntConstant(32768), 1); 679 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimShort, increment_[0], -1); 680 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 681 basic_[0]->ReplaceInput(conv, 1); 682 PerformInductionVarAnalysis(); 683 684 EXPECT_STREQ("((1) * i + ((-32768) + (1))):PrimShort", 685 GetInductionInfo(increment_[0], 0).c_str()); 686 // Trip-count undefined. 687 EXPECT_STREQ("", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 688 } 689 690 TEST_F(InductionVarAnalysisTest, CharLoopControl1) { 691 // Setup: 692 // for (char i = 0; i < 65535; i++) { // just fits! 693 // } 694 BuildLoopNest(1); 695 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 696 ifs->ReplaceInput(graph_->GetIntConstant(65535), 1); 697 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimChar, increment_[0], -1); 698 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 699 basic_[0]->ReplaceInput(conv, 1); 700 PerformInductionVarAnalysis(); 701 702 EXPECT_STREQ("((1) * i + (1)):PrimChar", GetInductionInfo(increment_[0], 0).c_str()); 703 // Trip-count. 704 EXPECT_STREQ("((65535) (TC-loop) ((0) < (65535)))", 705 GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 706 } 707 708 TEST_F(InductionVarAnalysisTest, CharLoopControl2) { 709 // Setup: 710 // for (char i = 0; i < 65536; i++) { // infinite loop! 711 // } 712 BuildLoopNest(1); 713 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 714 ifs->ReplaceInput(graph_->GetIntConstant(65536), 1); 715 HInstruction* conv = new(&allocator_) HTypeConversion(Primitive::kPrimChar, increment_[0], -1); 716 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 717 basic_[0]->ReplaceInput(conv, 1); 718 PerformInductionVarAnalysis(); 719 720 EXPECT_STREQ("((1) * i + (1)):PrimChar", GetInductionInfo(increment_[0], 0).c_str()); 721 // Trip-count undefined. 722 EXPECT_STREQ("", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str()); 723 } 724 725 } // namespace art 726
