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 OptimizingUnitTest { 31 public: 32 InductionVarAnalysisTest() 33 : iva_(nullptr), 34 entry_(nullptr), 35 return_(nullptr), 36 exit_(nullptr), 37 parameter_(nullptr), 38 constant0_(nullptr), 39 constant1_(nullptr), 40 constant2_(nullptr), 41 constant7_(nullptr), 42 constant100_(nullptr), 43 constantm1_(nullptr), 44 float_constant0_(nullptr) { 45 graph_ = CreateGraph(); 46 } 47 48 ~InductionVarAnalysisTest() { } 49 50 // Builds single for-loop at depth d. 51 void BuildForLoop(int d, int n) { 52 ASSERT_LT(d, n); 53 loop_preheader_[d] = new (GetAllocator()) HBasicBlock(graph_); 54 graph_->AddBlock(loop_preheader_[d]); 55 loop_header_[d] = new (GetAllocator()) HBasicBlock(graph_); 56 graph_->AddBlock(loop_header_[d]); 57 loop_preheader_[d]->AddSuccessor(loop_header_[d]); 58 if (d < (n - 1)) { 59 BuildForLoop(d + 1, n); 60 } 61 loop_body_[d] = new (GetAllocator()) HBasicBlock(graph_); 62 graph_->AddBlock(loop_body_[d]); 63 loop_body_[d]->AddSuccessor(loop_header_[d]); 64 if (d < (n - 1)) { 65 loop_header_[d]->AddSuccessor(loop_preheader_[d + 1]); 66 loop_header_[d + 1]->AddSuccessor(loop_body_[d]); 67 } else { 68 loop_header_[d]->AddSuccessor(loop_body_[d]); 69 } 70 } 71 72 // Builds a n-nested loop in CFG where each loop at depth 0 <= d < n 73 // is defined as "for (int i_d = 0; i_d < 100; i_d++)". Tests can further 74 // populate the loop with instructions to set up interesting scenarios. 75 void BuildLoopNest(int n) { 76 ASSERT_LE(n, 10); 77 graph_->SetNumberOfVRegs(n + 3); 78 79 // Build basic blocks with entry, nested loop, exit. 80 entry_ = new (GetAllocator()) HBasicBlock(graph_); 81 graph_->AddBlock(entry_); 82 BuildForLoop(0, n); 83 return_ = new (GetAllocator()) HBasicBlock(graph_); 84 graph_->AddBlock(return_); 85 exit_ = new (GetAllocator()) HBasicBlock(graph_); 86 graph_->AddBlock(exit_); 87 entry_->AddSuccessor(loop_preheader_[0]); 88 loop_header_[0]->AddSuccessor(return_); 89 return_->AddSuccessor(exit_); 90 graph_->SetEntryBlock(entry_); 91 graph_->SetExitBlock(exit_); 92 93 // Provide entry and exit instructions. 94 parameter_ = new (GetAllocator()) HParameterValue( 95 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference, true); 96 entry_->AddInstruction(parameter_); 97 constant0_ = graph_->GetIntConstant(0); 98 constant1_ = graph_->GetIntConstant(1); 99 constant2_ = graph_->GetIntConstant(2); 100 constant7_ = graph_->GetIntConstant(7); 101 constant100_ = graph_->GetIntConstant(100); 102 constantm1_ = graph_->GetIntConstant(-1); 103 float_constant0_ = graph_->GetFloatConstant(0.0f); 104 return_->AddInstruction(new (GetAllocator()) HReturnVoid()); 105 exit_->AddInstruction(new (GetAllocator()) HExit()); 106 107 // Provide loop instructions. 108 for (int d = 0; d < n; d++) { 109 basic_[d] = new (GetAllocator()) HPhi(GetAllocator(), d, 0, DataType::Type::kInt32); 110 loop_preheader_[d]->AddInstruction(new (GetAllocator()) HGoto()); 111 loop_header_[d]->AddPhi(basic_[d]); 112 HInstruction* compare = new (GetAllocator()) HLessThan(basic_[d], constant100_); 113 loop_header_[d]->AddInstruction(compare); 114 loop_header_[d]->AddInstruction(new (GetAllocator()) HIf(compare)); 115 increment_[d] = new (GetAllocator()) HAdd(DataType::Type::kInt32, basic_[d], constant1_); 116 loop_body_[d]->AddInstruction(increment_[d]); 117 loop_body_[d]->AddInstruction(new (GetAllocator()) HGoto()); 118 119 basic_[d]->AddInput(constant0_); 120 basic_[d]->AddInput(increment_[d]); 121 } 122 } 123 124 // Builds if-statement at depth d. 125 HPhi* BuildIf(int d, HBasicBlock** ifT, HBasicBlock** ifF) { 126 HBasicBlock* cond = new (GetAllocator()) HBasicBlock(graph_); 127 HBasicBlock* ifTrue = new (GetAllocator()) HBasicBlock(graph_); 128 HBasicBlock* ifFalse = new (GetAllocator()) HBasicBlock(graph_); 129 graph_->AddBlock(cond); 130 graph_->AddBlock(ifTrue); 131 graph_->AddBlock(ifFalse); 132 // Conditional split. 133 loop_header_[d]->ReplaceSuccessor(loop_body_[d], cond); 134 cond->AddSuccessor(ifTrue); 135 cond->AddSuccessor(ifFalse); 136 ifTrue->AddSuccessor(loop_body_[d]); 137 ifFalse->AddSuccessor(loop_body_[d]); 138 cond->AddInstruction(new (GetAllocator()) HIf(parameter_)); 139 *ifT = ifTrue; 140 *ifF = ifFalse; 141 142 HPhi* select_phi = new (GetAllocator()) HPhi(GetAllocator(), -1, 0, DataType::Type::kInt32); 143 loop_body_[d]->AddPhi(select_phi); 144 return select_phi; 145 } 146 147 // Inserts instruction right before increment at depth d. 148 HInstruction* InsertInstruction(HInstruction* instruction, int d) { 149 loop_body_[d]->InsertInstructionBefore(instruction, increment_[d]); 150 return instruction; 151 } 152 153 // Inserts a phi to loop header at depth d and returns it. 154 HPhi* InsertLoopPhi(int vreg, int d) { 155 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), vreg, 0, DataType::Type::kInt32); 156 loop_header_[d]->AddPhi(phi); 157 return phi; 158 } 159 160 // Inserts an array store with given `subscript` at depth d to 161 // enable tests to inspect the computed induction at that point easily. 162 HInstruction* InsertArrayStore(HInstruction* subscript, int d) { 163 // ArraySet is given a float value in order to avoid SsaBuilder typing 164 // it from the array's non-existent reference type info. 165 return InsertInstruction(new (GetAllocator()) HArraySet( 166 parameter_, subscript, float_constant0_, DataType::Type::kFloat32, 0), d); 167 } 168 169 // Returns induction information of instruction in loop at depth d. 170 std::string GetInductionInfo(HInstruction* instruction, int d) { 171 return HInductionVarAnalysis::InductionToString( 172 iva_->LookupInfo(loop_body_[d]->GetLoopInformation(), instruction)); 173 } 174 175 // Returns induction information of the trip-count of loop at depth d. 176 std::string GetTripCount(int d) { 177 HInstruction* control = loop_header_[d]->GetLastInstruction(); 178 DCHECK(control->IsIf()); 179 return GetInductionInfo(control, d); 180 } 181 182 // Returns true if instructions have identical induction. 183 bool HaveSameInduction(HInstruction* instruction1, HInstruction* instruction2) { 184 return HInductionVarAnalysis::InductionEqual( 185 iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction1), 186 iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction2)); 187 } 188 189 // Returns true for narrowing linear induction. 190 bool IsNarrowingLinear(HInstruction* instruction) { 191 return HInductionVarAnalysis::IsNarrowingLinear( 192 iva_->LookupInfo(loop_body_[0]->GetLoopInformation(), instruction)); 193 } 194 195 // Performs InductionVarAnalysis (after proper set up). 196 void PerformInductionVarAnalysis() { 197 graph_->BuildDominatorTree(); 198 iva_ = new (GetAllocator()) HInductionVarAnalysis(graph_); 199 iva_->Run(); 200 } 201 202 // General building fields. 203 HGraph* graph_; 204 HInductionVarAnalysis* iva_; 205 206 // Fixed basic blocks and instructions. 207 HBasicBlock* entry_; 208 HBasicBlock* return_; 209 HBasicBlock* exit_; 210 HInstruction* parameter_; // "this" 211 HInstruction* constant0_; 212 HInstruction* constant1_; 213 HInstruction* constant2_; 214 HInstruction* constant7_; 215 HInstruction* constant100_; 216 HInstruction* constantm1_; 217 HInstruction* float_constant0_; 218 219 // Loop specifics. 220 HBasicBlock* loop_preheader_[10]; 221 HBasicBlock* loop_header_[10]; 222 HBasicBlock* loop_body_[10]; 223 HInstruction* increment_[10]; 224 HPhi* basic_[10]; // "vreg_d", the "i_d" 225 }; 226 227 // 228 // The actual InductionVarAnalysis tests. 229 // 230 231 TEST_F(InductionVarAnalysisTest, ProperLoopSetup) { 232 // Setup: 233 // for (int i_0 = 0; i_0 < 100; i_0++) { 234 // .. 235 // for (int i_9 = 0; i_9 < 100; i_9++) { 236 // } 237 // .. 238 // } 239 BuildLoopNest(10); 240 graph_->BuildDominatorTree(); 241 242 ASSERT_EQ(entry_->GetLoopInformation(), nullptr); 243 for (int d = 0; d < 1; d++) { 244 ASSERT_EQ(loop_preheader_[d]->GetLoopInformation(), 245 (d == 0) ? nullptr 246 : loop_header_[d - 1]->GetLoopInformation()); 247 ASSERT_NE(loop_header_[d]->GetLoopInformation(), nullptr); 248 ASSERT_NE(loop_body_[d]->GetLoopInformation(), nullptr); 249 ASSERT_EQ(loop_header_[d]->GetLoopInformation(), 250 loop_body_[d]->GetLoopInformation()); 251 } 252 ASSERT_EQ(exit_->GetLoopInformation(), nullptr); 253 } 254 255 TEST_F(InductionVarAnalysisTest, FindBasicInduction) { 256 // Setup: 257 // for (int i = 0; i < 100; i++) { 258 // a[i] = 0; 259 // } 260 BuildLoopNest(1); 261 HInstruction* store = InsertArrayStore(basic_[0], 0); 262 PerformInductionVarAnalysis(); 263 264 EXPECT_STREQ("((1) * i + (0)):Int32", GetInductionInfo(store->InputAt(1), 0).c_str()); 265 EXPECT_STREQ("((1) * i + (1)):Int32", GetInductionInfo(increment_[0], 0).c_str()); 266 267 // Offset matters! 268 EXPECT_FALSE(HaveSameInduction(store->InputAt(1), increment_[0])); 269 270 // Trip-count. 271 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", GetTripCount(0).c_str()); 272 } 273 274 TEST_F(InductionVarAnalysisTest, FindDerivedInduction) { 275 // Setup: 276 // for (int i = 0; i < 100; i++) { 277 // t = 100 + i; 278 // t = 100 - i; 279 // t = 100 * i; 280 // t = i << 1; 281 // t = - i; 282 // } 283 BuildLoopNest(1); 284 HInstruction* add = InsertInstruction( 285 new (GetAllocator()) HAdd(DataType::Type::kInt32, constant100_, basic_[0]), 0); 286 HInstruction* sub = InsertInstruction( 287 new (GetAllocator()) HSub(DataType::Type::kInt32, constant100_, basic_[0]), 0); 288 HInstruction* mul = InsertInstruction( 289 new (GetAllocator()) HMul(DataType::Type::kInt32, constant100_, basic_[0]), 0); 290 HInstruction* shl = InsertInstruction( 291 new (GetAllocator()) HShl(DataType::Type::kInt32, basic_[0], constant1_), 0); 292 HInstruction* neg = InsertInstruction( 293 new (GetAllocator()) HNeg(DataType::Type::kInt32, basic_[0]), 0); 294 PerformInductionVarAnalysis(); 295 296 EXPECT_STREQ("((1) * i + (100)):Int32", GetInductionInfo(add, 0).c_str()); 297 EXPECT_STREQ("(( - (1)) * i + (100)):Int32", GetInductionInfo(sub, 0).c_str()); 298 EXPECT_STREQ("((100) * i + (0)):Int32", GetInductionInfo(mul, 0).c_str()); 299 EXPECT_STREQ("((2) * i + (0)):Int32", GetInductionInfo(shl, 0).c_str()); 300 EXPECT_STREQ("(( - (1)) * i + (0)):Int32", GetInductionInfo(neg, 0).c_str()); 301 } 302 303 TEST_F(InductionVarAnalysisTest, FindChainInduction) { 304 // Setup: 305 // k = 0; 306 // for (int i = 0; i < 100; i++) { 307 // k = k + 100; 308 // a[k] = 0; 309 // k = k - 1; 310 // a[k] = 0; 311 // } 312 BuildLoopNest(1); 313 HPhi* k_header = InsertLoopPhi(0, 0); 314 k_header->AddInput(constant0_); 315 316 HInstruction* add = InsertInstruction( 317 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant100_), 0); 318 HInstruction* store1 = InsertArrayStore(add, 0); 319 HInstruction* sub = InsertInstruction( 320 new (GetAllocator()) HSub(DataType::Type::kInt32, add, constant1_), 0); 321 HInstruction* store2 = InsertArrayStore(sub, 0); 322 k_header->AddInput(sub); 323 PerformInductionVarAnalysis(); 324 325 EXPECT_STREQ("(((100) - (1)) * i + (0)):Int32", 326 GetInductionInfo(k_header, 0).c_str()); 327 EXPECT_STREQ("(((100) - (1)) * i + (100)):Int32", 328 GetInductionInfo(store1->InputAt(1), 0).c_str()); 329 EXPECT_STREQ("(((100) - (1)) * i + ((100) - (1))):Int32", 330 GetInductionInfo(store2->InputAt(1), 0).c_str()); 331 } 332 333 TEST_F(InductionVarAnalysisTest, FindTwoWayBasicInduction) { 334 // Setup: 335 // k = 0; 336 // for (int i = 0; i < 100; i++) { 337 // if () k = k + 1; 338 // else k = k + 1; 339 // a[k] = 0; 340 // } 341 BuildLoopNest(1); 342 HPhi* k_header = InsertLoopPhi(0, 0); 343 k_header->AddInput(constant0_); 344 345 HBasicBlock* ifTrue; 346 HBasicBlock* ifFalse; 347 HPhi* k_body = BuildIf(0, &ifTrue, &ifFalse); 348 349 // True-branch. 350 HInstruction* inc1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant1_); 351 ifTrue->AddInstruction(inc1); 352 k_body->AddInput(inc1); 353 // False-branch. 354 HInstruction* inc2 = new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant1_); 355 ifFalse->AddInstruction(inc2); 356 k_body->AddInput(inc2); 357 // Merge over a phi. 358 HInstruction* store = InsertArrayStore(k_body, 0); 359 k_header->AddInput(k_body); 360 PerformInductionVarAnalysis(); 361 362 EXPECT_STREQ("((1) * i + (0)):Int32", GetInductionInfo(k_header, 0).c_str()); 363 EXPECT_STREQ("((1) * i + (1)):Int32", GetInductionInfo(store->InputAt(1), 0).c_str()); 364 365 // Both increments get same induction. 366 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc1)); 367 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc2)); 368 } 369 370 TEST_F(InductionVarAnalysisTest, FindTwoWayDerivedInduction) { 371 // Setup: 372 // for (int i = 0; i < 100; i++) { 373 // if () k = i + 1; 374 // else k = i + 1; 375 // a[k] = 0; 376 // } 377 BuildLoopNest(1); 378 HBasicBlock* ifTrue; 379 HBasicBlock* ifFalse; 380 HPhi* k = BuildIf(0, &ifTrue, &ifFalse); 381 382 // True-branch. 383 HInstruction* inc1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, basic_[0], constant1_); 384 ifTrue->AddInstruction(inc1); 385 k->AddInput(inc1); 386 // False-branch. 387 HInstruction* inc2 = new (GetAllocator()) HAdd(DataType::Type::kInt32, basic_[0], constant1_); 388 ifFalse->AddInstruction(inc2); 389 k->AddInput(inc2); 390 // Merge over a phi. 391 HInstruction* store = InsertArrayStore(k, 0); 392 PerformInductionVarAnalysis(); 393 394 EXPECT_STREQ("((1) * i + (1)):Int32", GetInductionInfo(store->InputAt(1), 0).c_str()); 395 396 // Both increments get same induction. 397 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc1)); 398 EXPECT_TRUE(HaveSameInduction(store->InputAt(1), inc2)); 399 } 400 401 TEST_F(InductionVarAnalysisTest, AddLinear) { 402 // Setup: 403 // for (int i = 0; i < 100; i++) { 404 // t1 = i + i; 405 // t2 = 7 + i; 406 // t3 = t1 + t2; 407 // } 408 BuildLoopNest(1); 409 410 HInstruction* add1 = InsertInstruction( 411 new (GetAllocator()) HAdd(DataType::Type::kInt32, basic_[0], basic_[0]), 0); 412 HInstruction* add2 = InsertInstruction( 413 new (GetAllocator()) HAdd(DataType::Type::kInt32, constant7_, basic_[0]), 0); 414 HInstruction* add3 = InsertInstruction( 415 new (GetAllocator()) HAdd(DataType::Type::kInt32, add1, add2), 0); 416 PerformInductionVarAnalysis(); 417 418 EXPECT_STREQ("((1) * i + (0)):Int32", GetInductionInfo(basic_[0], 0).c_str()); 419 EXPECT_STREQ("(((1) + (1)) * i + (0)):Int32", GetInductionInfo(add1, 0).c_str()); 420 EXPECT_STREQ("((1) * i + (7)):Int32", GetInductionInfo(add2, 0).c_str()); 421 EXPECT_STREQ("((((1) + (1)) + (1)) * i + (7)):Int32", GetInductionInfo(add3, 0).c_str()); 422 } 423 424 TEST_F(InductionVarAnalysisTest, FindPolynomialInduction) { 425 // Setup: 426 // k = 1; 427 // for (int i = 0; i < 100; i++) { 428 // t = i * 2; 429 // t = 100 + t 430 // k = t + k; // polynomial 431 // } 432 BuildLoopNest(1); 433 HPhi* k_header = InsertLoopPhi(0, 0); 434 k_header->AddInput(constant1_); 435 436 HInstruction* mul = InsertInstruction( 437 new (GetAllocator()) HMul(DataType::Type::kInt32, basic_[0], constant2_), 0); 438 HInstruction* add = InsertInstruction( 439 new (GetAllocator()) HAdd(DataType::Type::kInt32, constant100_, mul), 0); 440 HInstruction* pol = InsertInstruction( 441 new (GetAllocator()) HAdd(DataType::Type::kInt32, add, k_header), 0); 442 k_header->AddInput(pol); 443 PerformInductionVarAnalysis(); 444 445 // Note, only the phi in the cycle and the base linear induction are classified. 446 EXPECT_STREQ("poly(sum_lt(((2) * i + (100)):Int32) + (1)):Int32", 447 GetInductionInfo(k_header, 0).c_str()); 448 EXPECT_STREQ("((2) * i + (100)):Int32", GetInductionInfo(add, 0).c_str()); 449 EXPECT_STREQ("", GetInductionInfo(pol, 0).c_str()); 450 } 451 452 TEST_F(InductionVarAnalysisTest, FindPolynomialInductionAndDerived) { 453 // Setup: 454 // k = 1; 455 // for (int i = 0; i < 100; i++) { 456 // t = k + 100; 457 // t = k - 1; 458 // t = - t 459 // t = k * 2; 460 // t = k << 2; 461 // k = k + i; // polynomial 462 // } 463 BuildLoopNest(1); 464 HPhi* k_header = InsertLoopPhi(0, 0); 465 k_header->AddInput(constant1_); 466 467 HInstruction* add = InsertInstruction( 468 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant100_), 0); 469 HInstruction* sub = InsertInstruction( 470 new (GetAllocator()) HSub(DataType::Type::kInt32, k_header, constant1_), 0); 471 HInstruction* neg = InsertInstruction( 472 new (GetAllocator()) HNeg(DataType::Type::kInt32, sub), 0); 473 HInstruction* mul = InsertInstruction( 474 new (GetAllocator()) HMul(DataType::Type::kInt32, k_header, constant2_), 0); 475 HInstruction* shl = InsertInstruction( 476 new (GetAllocator()) HShl(DataType::Type::kInt32, k_header, constant2_), 0); 477 HInstruction* pol = InsertInstruction( 478 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, basic_[0]), 0); 479 k_header->AddInput(pol); 480 PerformInductionVarAnalysis(); 481 482 // Note, only the phi in the cycle and derived are classified. 483 EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):Int32) + (1)):Int32", 484 GetInductionInfo(k_header, 0).c_str()); 485 EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):Int32) + ((1) + (100))):Int32", 486 GetInductionInfo(add, 0).c_str()); 487 EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):Int32) + ((1) - (1))):Int32", 488 GetInductionInfo(sub, 0).c_str()); 489 EXPECT_STREQ("poly(sum_lt((( - (1)) * i + (0)):Int32) + ((1) - (1))):Int32", 490 GetInductionInfo(neg, 0).c_str()); 491 EXPECT_STREQ("poly(sum_lt(((2) * i + (0)):Int32) + (2)):Int32", 492 GetInductionInfo(mul, 0).c_str()); 493 EXPECT_STREQ("poly(sum_lt(((4) * i + (0)):Int32) + (4)):Int32", 494 GetInductionInfo(shl, 0).c_str()); 495 EXPECT_STREQ("", GetInductionInfo(pol, 0).c_str()); 496 } 497 498 TEST_F(InductionVarAnalysisTest, AddPolynomial) { 499 // Setup: 500 // k = 7; 501 // for (int i = 0; i < 100; i++) { 502 // t = k + k; 503 // t = t + k; 504 // k = k + i 505 // } 506 BuildLoopNest(1); 507 HPhi* k_header = InsertLoopPhi(0, 0); 508 k_header->AddInput(constant7_); 509 510 HInstruction* add1 = InsertInstruction( 511 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, k_header), 0); 512 HInstruction* add2 = InsertInstruction( 513 new (GetAllocator()) HAdd(DataType::Type::kInt32, add1, k_header), 0); 514 HInstruction* add3 = InsertInstruction( 515 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, basic_[0]), 0); 516 k_header->AddInput(add3); 517 PerformInductionVarAnalysis(); 518 519 // Note, only the phi in the cycle and added-derived are classified. 520 EXPECT_STREQ("poly(sum_lt(((1) * i + (0)):Int32) + (7)):Int32", 521 GetInductionInfo(k_header, 0).c_str()); 522 EXPECT_STREQ("poly(sum_lt((((1) + (1)) * i + (0)):Int32) + ((7) + (7))):Int32", 523 GetInductionInfo(add1, 0).c_str()); 524 EXPECT_STREQ( 525 "poly(sum_lt(((((1) + (1)) + (1)) * i + (0)):Int32) + (((7) + (7)) + (7))):Int32", 526 GetInductionInfo(add2, 0).c_str()); 527 EXPECT_STREQ("", GetInductionInfo(add3, 0).c_str()); 528 } 529 530 TEST_F(InductionVarAnalysisTest, FindGeometricMulInduction) { 531 // Setup: 532 // k = 1; 533 // for (int i = 0; i < 100; i++) { 534 // k = k * 100; // geometric (x 100) 535 // } 536 BuildLoopNest(1); 537 HPhi* k_header = InsertLoopPhi(0, 0); 538 k_header->AddInput(constant1_); 539 540 HInstruction* mul = InsertInstruction( 541 new (GetAllocator()) HMul(DataType::Type::kInt32, k_header, constant100_), 0); 542 k_header->AddInput(mul); 543 PerformInductionVarAnalysis(); 544 545 EXPECT_STREQ("geo((1) * 100 ^ i + (0)):Int32", GetInductionInfo(k_header, 0).c_str()); 546 EXPECT_STREQ("geo((100) * 100 ^ i + (0)):Int32", GetInductionInfo(mul, 0).c_str()); 547 } 548 549 TEST_F(InductionVarAnalysisTest, FindGeometricShlInductionAndDerived) { 550 // Setup: 551 // k = 1; 552 // for (int i = 0; i < 100; i++) { 553 // t = k + 1; 554 // k = k << 1; // geometric (x 2) 555 // t = k + 100; 556 // t = k - 1; 557 // t = - t; 558 // t = k * 2; 559 // t = k << 2; 560 // } 561 BuildLoopNest(1); 562 HPhi* k_header = InsertLoopPhi(0, 0); 563 k_header->AddInput(constant1_); 564 565 HInstruction* add1 = InsertInstruction( 566 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant1_), 0); 567 HInstruction* shl1 = InsertInstruction( 568 new (GetAllocator()) HShl(DataType::Type::kInt32, k_header, constant1_), 0); 569 HInstruction* add2 = InsertInstruction( 570 new (GetAllocator()) HAdd(DataType::Type::kInt32, shl1, constant100_), 0); 571 HInstruction* sub = InsertInstruction( 572 new (GetAllocator()) HSub(DataType::Type::kInt32, shl1, constant1_), 0); 573 HInstruction* neg = InsertInstruction( 574 new (GetAllocator()) HNeg(DataType::Type::kInt32, sub), 0); 575 HInstruction* mul = InsertInstruction( 576 new (GetAllocator()) HMul(DataType::Type::kInt32, shl1, constant2_), 0); 577 HInstruction* shl2 = InsertInstruction( 578 new (GetAllocator()) HShl(DataType::Type::kInt32, shl1, constant2_), 0); 579 k_header->AddInput(shl1); 580 PerformInductionVarAnalysis(); 581 582 EXPECT_STREQ("geo((1) * 2 ^ i + (0)):Int32", GetInductionInfo(k_header, 0).c_str()); 583 EXPECT_STREQ("geo((1) * 2 ^ i + (1)):Int32", GetInductionInfo(add1, 0).c_str()); 584 EXPECT_STREQ("geo((2) * 2 ^ i + (0)):Int32", GetInductionInfo(shl1, 0).c_str()); 585 EXPECT_STREQ("geo((2) * 2 ^ i + (100)):Int32", GetInductionInfo(add2, 0).c_str()); 586 EXPECT_STREQ("geo((2) * 2 ^ i + ((0) - (1))):Int32", GetInductionInfo(sub, 0).c_str()); 587 EXPECT_STREQ("geo(( - (2)) * 2 ^ i + ( - ((0) - (1)))):Int32", 588 GetInductionInfo(neg, 0).c_str()); 589 EXPECT_STREQ("geo(((2) * (2)) * 2 ^ i + (0)):Int32", GetInductionInfo(mul, 0).c_str()); 590 EXPECT_STREQ("geo(((2) * (4)) * 2 ^ i + (0)):Int32", GetInductionInfo(shl2, 0).c_str()); 591 } 592 593 TEST_F(InductionVarAnalysisTest, FindGeometricDivInductionAndDerived) { 594 // Setup: 595 // k = 1; 596 // for (int i = 0; i < 100; i++) { 597 // t = k + 100; 598 // t = k - 1; 599 // t = - t 600 // t = k * 2; 601 // t = k << 2; 602 // k = k / 100; // geometric (/ 100) 603 // } 604 BuildLoopNest(1); 605 HPhi* k_header = InsertLoopPhi(0, 0); 606 k_header->AddInput(constant1_); 607 608 HInstruction* add = InsertInstruction( 609 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant100_), 0); 610 HInstruction* sub = InsertInstruction( 611 new (GetAllocator()) HSub(DataType::Type::kInt32, k_header, constant1_), 0); 612 HInstruction* neg = InsertInstruction( 613 new (GetAllocator()) HNeg(DataType::Type::kInt32, sub), 0); 614 HInstruction* mul = InsertInstruction( 615 new (GetAllocator()) HMul(DataType::Type::kInt32, k_header, constant2_), 0); 616 HInstruction* shl = InsertInstruction( 617 new (GetAllocator()) HShl(DataType::Type::kInt32, k_header, constant2_), 0); 618 HInstruction* div = InsertInstruction( 619 new (GetAllocator()) HDiv(DataType::Type::kInt32, k_header, constant100_, kNoDexPc), 0); 620 k_header->AddInput(div); 621 PerformInductionVarAnalysis(); 622 623 // Note, only the phi in the cycle and direct additive derived are classified. 624 EXPECT_STREQ("geo((1) * 100 ^ -i + (0)):Int32", GetInductionInfo(k_header, 0).c_str()); 625 EXPECT_STREQ("geo((1) * 100 ^ -i + (100)):Int32", GetInductionInfo(add, 0).c_str()); 626 EXPECT_STREQ("geo((1) * 100 ^ -i + ((0) - (1))):Int32", GetInductionInfo(sub, 0).c_str()); 627 EXPECT_STREQ("", GetInductionInfo(neg, 0).c_str()); 628 EXPECT_STREQ("", GetInductionInfo(mul, 0).c_str()); 629 EXPECT_STREQ("", GetInductionInfo(shl, 0).c_str()); 630 EXPECT_STREQ("", GetInductionInfo(div, 0).c_str()); 631 } 632 633 TEST_F(InductionVarAnalysisTest, FindGeometricShrInduction) { 634 // Setup: 635 // k = 100; 636 // for (int i = 0; i < 100; i++) { 637 // k = k >> 1; // geometric (/ 2) 638 // } 639 BuildLoopNest(1); 640 HPhi* k_header = InsertLoopPhi(0, 0); 641 k_header->AddInput(constant100_); 642 643 HInstruction* shr = InsertInstruction( 644 new (GetAllocator()) HShr(DataType::Type::kInt32, k_header, constant1_), 0); 645 k_header->AddInput(shr); 646 PerformInductionVarAnalysis(); 647 648 // Note, only the phi in the cycle is classified. 649 EXPECT_STREQ("geo((100) * 2 ^ -i + (0)):Int32", GetInductionInfo(k_header, 0).c_str()); 650 EXPECT_STREQ("", GetInductionInfo(shr, 0).c_str()); 651 } 652 653 TEST_F(InductionVarAnalysisTest, FindNotGeometricShrInduction) { 654 // Setup: 655 // k = -1; 656 // for (int i = 0; i < 100; i++) { 657 // k = k >> 1; // initial value is negative 658 // } 659 BuildLoopNest(1); 660 HPhi* k_header = InsertLoopPhi(0, 0); 661 k_header->AddInput(constantm1_); 662 663 HInstruction* shr = InsertInstruction( 664 new (GetAllocator()) HShr(DataType::Type::kInt32, k_header, constant1_), 0); 665 k_header->AddInput(shr); 666 PerformInductionVarAnalysis(); 667 668 EXPECT_STREQ("", GetInductionInfo(k_header, 0).c_str()); 669 EXPECT_STREQ("", GetInductionInfo(shr, 0).c_str()); 670 } 671 672 TEST_F(InductionVarAnalysisTest, FindRemWrapAroundInductionAndDerived) { 673 // Setup: 674 // k = 100; 675 // for (int i = 0; i < 100; i++) { 676 // t = k + 100; 677 // t = k - 1; 678 // t = -t 679 // t = k * 2; 680 // t = k << 2; 681 // k = k % 7; 682 // } 683 BuildLoopNest(1); 684 HPhi* k_header = InsertLoopPhi(0, 0); 685 k_header->AddInput(constant100_); 686 687 HInstruction* add = InsertInstruction( 688 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant100_), 0); 689 HInstruction* sub = InsertInstruction( 690 new (GetAllocator()) HSub(DataType::Type::kInt32, k_header, constant1_), 0); 691 HInstruction* neg = InsertInstruction( 692 new (GetAllocator()) HNeg(DataType::Type::kInt32, sub), 0); 693 HInstruction* mul = InsertInstruction( 694 new (GetAllocator()) HMul(DataType::Type::kInt32, k_header, constant2_), 0); 695 HInstruction* shl = InsertInstruction( 696 new (GetAllocator()) HShl(DataType::Type::kInt32, k_header, constant2_), 0); 697 HInstruction* rem = InsertInstruction( 698 new (GetAllocator()) HRem(DataType::Type::kInt32, k_header, constant7_, kNoDexPc), 0); 699 k_header->AddInput(rem); 700 PerformInductionVarAnalysis(); 701 702 // Note, only the phi in the cycle and derived are classified. 703 EXPECT_STREQ("wrap((100), ((100) % (7))):Int32", GetInductionInfo(k_header, 0).c_str()); 704 EXPECT_STREQ("wrap(((100) + (100)), (((100) % (7)) + (100))):Int32", 705 GetInductionInfo(add, 0).c_str()); 706 EXPECT_STREQ("wrap(((100) - (1)), (((100) % (7)) - (1))):Int32", 707 GetInductionInfo(sub, 0).c_str()); 708 EXPECT_STREQ("wrap(( - ((100) - (1))), ( - (((100) % (7)) - (1)))):Int32", 709 GetInductionInfo(neg, 0).c_str()); 710 EXPECT_STREQ("wrap(((100) * (2)), (((100) % (7)) * (2))):Int32", 711 GetInductionInfo(mul, 0).c_str()); 712 EXPECT_STREQ("wrap(((100) * (4)), (((100) % (7)) * (4))):Int32", 713 GetInductionInfo(shl, 0).c_str()); 714 EXPECT_STREQ("", GetInductionInfo(rem, 0).c_str()); 715 } 716 717 TEST_F(InductionVarAnalysisTest, FindFirstOrderWrapAroundInduction) { 718 // Setup: 719 // k = 0; 720 // for (int i = 0; i < 100; i++) { 721 // a[k] = 0; 722 // k = 100 - i; 723 // } 724 BuildLoopNest(1); 725 HPhi* k_header = InsertLoopPhi(0, 0); 726 k_header->AddInput(constant0_); 727 728 HInstruction* store = InsertArrayStore(k_header, 0); 729 HInstruction* sub = InsertInstruction( 730 new (GetAllocator()) HSub(DataType::Type::kInt32, constant100_, basic_[0]), 0); 731 k_header->AddInput(sub); 732 PerformInductionVarAnalysis(); 733 734 EXPECT_STREQ("wrap((0), (( - (1)) * i + (100)):Int32):Int32", 735 GetInductionInfo(k_header, 0).c_str()); 736 EXPECT_STREQ("wrap((0), (( - (1)) * i + (100)):Int32):Int32", 737 GetInductionInfo(store->InputAt(1), 0).c_str()); 738 EXPECT_STREQ("(( - (1)) * i + (100)):Int32", GetInductionInfo(sub, 0).c_str()); 739 } 740 741 TEST_F(InductionVarAnalysisTest, FindSecondOrderWrapAroundInduction) { 742 // Setup: 743 // k = 0; 744 // t = 100; 745 // for (int i = 0; i < 100; i++) { 746 // a[k] = 0; 747 // k = t; 748 // t = 100 - i; 749 // } 750 BuildLoopNest(1); 751 HPhi* k_header = InsertLoopPhi(0, 0); 752 k_header->AddInput(constant0_); 753 HPhi* t = InsertLoopPhi(1, 0); 754 t->AddInput(constant100_); 755 756 HInstruction* store = InsertArrayStore(k_header, 0); 757 k_header->AddInput(t); 758 HInstruction* sub = InsertInstruction( 759 new (GetAllocator()) HSub(DataType::Type::kInt32, constant100_, basic_[0], 0), 0); 760 t->AddInput(sub); 761 PerformInductionVarAnalysis(); 762 763 EXPECT_STREQ("wrap((0), wrap((100), (( - (1)) * i + (100)):Int32):Int32):Int32", 764 GetInductionInfo(store->InputAt(1), 0).c_str()); 765 } 766 767 TEST_F(InductionVarAnalysisTest, FindWrapAroundDerivedInduction) { 768 // Setup: 769 // k = 0; 770 // for (int i = 0; i < 100; i++) { 771 // t = k + 100; 772 // t = k - 100; 773 // t = k * 100; 774 // t = k << 1; 775 // t = - k; 776 // k = i << 1; 777 // t = - k; 778 // } 779 BuildLoopNest(1); 780 HPhi* k_header = InsertLoopPhi(0, 0); 781 k_header->AddInput(constant0_); 782 783 HInstruction* add = InsertInstruction( 784 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant100_), 0); 785 HInstruction* sub = InsertInstruction( 786 new (GetAllocator()) HSub(DataType::Type::kInt32, k_header, constant100_), 0); 787 HInstruction* mul = InsertInstruction( 788 new (GetAllocator()) HMul(DataType::Type::kInt32, k_header, constant100_), 0); 789 HInstruction* shl1 = InsertInstruction( 790 new (GetAllocator()) HShl(DataType::Type::kInt32, k_header, constant1_), 0); 791 HInstruction* neg1 = InsertInstruction( 792 new (GetAllocator()) HNeg(DataType::Type::kInt32, k_header), 0); 793 HInstruction* shl2 = InsertInstruction( 794 new (GetAllocator()) HShl(DataType::Type::kInt32, basic_[0], constant1_), 0); 795 HInstruction* neg2 = InsertInstruction( 796 new (GetAllocator()) HNeg(DataType::Type::kInt32, shl2), 0); 797 k_header->AddInput(shl2); 798 PerformInductionVarAnalysis(); 799 800 EXPECT_STREQ("wrap((100), ((2) * i + (100)):Int32):Int32", 801 GetInductionInfo(add, 0).c_str()); 802 EXPECT_STREQ("wrap(((0) - (100)), ((2) * i + ((0) - (100))):Int32):Int32", 803 GetInductionInfo(sub, 0).c_str()); 804 EXPECT_STREQ("wrap((0), (((2) * (100)) * i + (0)):Int32):Int32", 805 GetInductionInfo(mul, 0).c_str()); 806 EXPECT_STREQ("wrap((0), (((2) * (2)) * i + (0)):Int32):Int32", 807 GetInductionInfo(shl1, 0).c_str()); 808 EXPECT_STREQ("wrap((0), (( - (2)) * i + (0)):Int32):Int32", 809 GetInductionInfo(neg1, 0).c_str()); 810 EXPECT_STREQ("((2) * i + (0)):Int32", GetInductionInfo(shl2, 0).c_str()); 811 EXPECT_STREQ("(( - (2)) * i + (0)):Int32", GetInductionInfo(neg2, 0).c_str()); 812 } 813 814 TEST_F(InductionVarAnalysisTest, FindPeriodicInduction) { 815 // Setup: 816 // k = 0; 817 // t = 100; 818 // for (int i = 0; i < 100; i++) { 819 // a[k] = 0; 820 // a[t] = 0; 821 // // Swap t <-> k. 822 // d = t; 823 // t = k; 824 // k = d; 825 // } 826 BuildLoopNest(1); 827 HPhi* k_header = InsertLoopPhi(0, 0); 828 k_header->AddInput(constant0_); 829 HPhi* t = InsertLoopPhi(1, 0); 830 t->AddInput(constant100_); 831 832 HInstruction* store1 = InsertArrayStore(k_header, 0); 833 HInstruction* store2 = InsertArrayStore(t, 0); 834 k_header->AddInput(t); 835 t->AddInput(k_header); 836 PerformInductionVarAnalysis(); 837 838 EXPECT_STREQ("periodic((0), (100)):Int32", GetInductionInfo(store1->InputAt(1), 0).c_str()); 839 EXPECT_STREQ("periodic((100), (0)):Int32", GetInductionInfo(store2->InputAt(1), 0).c_str()); 840 } 841 842 TEST_F(InductionVarAnalysisTest, FindIdiomaticPeriodicInduction) { 843 // Setup: 844 // k = 0; 845 // for (int i = 0; i < 100; i++) { 846 // a[k] = 0; 847 // k = 1 - k; 848 // } 849 BuildLoopNest(1); 850 HPhi* k_header = InsertLoopPhi(0, 0); 851 k_header->AddInput(constant0_); 852 853 HInstruction* store = InsertArrayStore(k_header, 0); 854 HInstruction* sub = InsertInstruction( 855 new (GetAllocator()) HSub(DataType::Type::kInt32, constant1_, k_header), 0); 856 k_header->AddInput(sub); 857 PerformInductionVarAnalysis(); 858 859 EXPECT_STREQ("periodic((0), (1)):Int32", GetInductionInfo(store->InputAt(1), 0).c_str()); 860 EXPECT_STREQ("periodic((1), (0)):Int32", GetInductionInfo(sub, 0).c_str()); 861 } 862 863 TEST_F(InductionVarAnalysisTest, FindXorPeriodicInduction) { 864 // Setup: 865 // k = 0; 866 // for (int i = 0; i < 100; i++) { 867 // a[k] = 0; 868 // k = k ^ 1; 869 // } 870 BuildLoopNest(1); 871 HPhi* k_header = InsertLoopPhi(0, 0); 872 k_header->AddInput(constant0_); 873 874 HInstruction* store = InsertArrayStore(k_header, 0); 875 HInstruction* x = InsertInstruction( 876 new (GetAllocator()) HXor(DataType::Type::kInt32, k_header, constant1_), 0); 877 k_header->AddInput(x); 878 PerformInductionVarAnalysis(); 879 880 EXPECT_STREQ("periodic((0), (1)):Int32", GetInductionInfo(store->InputAt(1), 0).c_str()); 881 EXPECT_STREQ("periodic((1), (0)):Int32", GetInductionInfo(x, 0).c_str()); 882 } 883 884 TEST_F(InductionVarAnalysisTest, FindXorConstantLeftPeriodicInduction) { 885 // Setup: 886 // k = 1; 887 // for (int i = 0; i < 100; i++) { 888 // k = 1 ^ k; 889 // } 890 BuildLoopNest(1); 891 HPhi* k_header = InsertLoopPhi(0, 0); 892 k_header->AddInput(constant1_); 893 894 HInstruction* x = InsertInstruction( 895 new (GetAllocator()) HXor(DataType::Type::kInt32, constant1_, k_header), 0); 896 k_header->AddInput(x); 897 PerformInductionVarAnalysis(); 898 899 EXPECT_STREQ("periodic((1), ((1) ^ (1))):Int32", GetInductionInfo(k_header, 0).c_str()); 900 EXPECT_STREQ("periodic(((1) ^ (1)), (1)):Int32", GetInductionInfo(x, 0).c_str()); 901 } 902 903 TEST_F(InductionVarAnalysisTest, FindXor100PeriodicInduction) { 904 // Setup: 905 // k = 1; 906 // for (int i = 0; i < 100; i++) { 907 // k = k ^ 100; 908 // } 909 BuildLoopNest(1); 910 HPhi* k_header = InsertLoopPhi(0, 0); 911 k_header->AddInput(constant1_); 912 913 HInstruction* x = InsertInstruction( 914 new (GetAllocator()) HXor(DataType::Type::kInt32, k_header, constant100_), 0); 915 k_header->AddInput(x); 916 PerformInductionVarAnalysis(); 917 918 EXPECT_STREQ("periodic((1), ((1) ^ (100))):Int32", GetInductionInfo(k_header, 0).c_str()); 919 EXPECT_STREQ("periodic(((1) ^ (100)), (1)):Int32", GetInductionInfo(x, 0).c_str()); 920 } 921 922 TEST_F(InductionVarAnalysisTest, FindBooleanEqPeriodicInduction) { 923 // Setup: 924 // k = 0; 925 // for (int i = 0; i < 100; i++) { 926 // k = (k == 0); 927 // } 928 BuildLoopNest(1); 929 HPhi* k_header = InsertLoopPhi(0, 0); 930 k_header->AddInput(constant0_); 931 932 HInstruction* x = InsertInstruction(new (GetAllocator()) HEqual(k_header, constant0_), 0); 933 k_header->AddInput(x); 934 PerformInductionVarAnalysis(); 935 936 EXPECT_STREQ("periodic((0), (1)):Bool", GetInductionInfo(k_header, 0).c_str()); 937 EXPECT_STREQ("periodic((1), (0)):Bool", GetInductionInfo(x, 0).c_str()); 938 } 939 940 TEST_F(InductionVarAnalysisTest, FindBooleanEqConstantLeftPeriodicInduction) { 941 // Setup: 942 // k = 0; 943 // for (int i = 0; i < 100; i++) { 944 // k = (0 == k); 945 // } 946 BuildLoopNest(1); 947 HPhi* k_header = InsertLoopPhi(0, 0); 948 k_header->AddInput(constant0_); 949 950 HInstruction* x = InsertInstruction(new (GetAllocator()) HEqual(constant0_, k_header), 0); 951 k_header->AddInput(x); 952 PerformInductionVarAnalysis(); 953 954 EXPECT_STREQ("periodic((0), (1)):Bool", GetInductionInfo(k_header, 0).c_str()); 955 EXPECT_STREQ("periodic((1), (0)):Bool", GetInductionInfo(x, 0).c_str()); 956 } 957 958 TEST_F(InductionVarAnalysisTest, FindBooleanNePeriodicInduction) { 959 // Setup: 960 // k = 0; 961 // for (int i = 0; i < 100; i++) { 962 // k = (k != 1); 963 // } 964 BuildLoopNest(1); 965 HPhi* k_header = InsertLoopPhi(0, 0); 966 k_header->AddInput(constant0_); 967 968 HInstruction* x = InsertInstruction(new (GetAllocator()) HNotEqual(k_header, constant1_), 0); 969 k_header->AddInput(x); 970 PerformInductionVarAnalysis(); 971 972 EXPECT_STREQ("periodic((0), (1)):Bool", GetInductionInfo(k_header, 0).c_str()); 973 EXPECT_STREQ("periodic((1), (0)):Bool", GetInductionInfo(x, 0).c_str()); 974 } 975 976 TEST_F(InductionVarAnalysisTest, FindBooleanNeConstantLeftPeriodicInduction) { 977 // Setup: 978 // k = 0; 979 // for (int i = 0; i < 100; i++) { 980 // k = (1 != k); 981 // } 982 BuildLoopNest(1); 983 HPhi* k_header = InsertLoopPhi(0, 0); 984 k_header->AddInput(constant0_); 985 986 HInstruction* x = InsertInstruction(new (GetAllocator()) HNotEqual(constant1_, k_header), 0); 987 k_header->AddInput(x); 988 PerformInductionVarAnalysis(); 989 990 EXPECT_STREQ("periodic((0), (1)):Bool", GetInductionInfo(k_header, 0).c_str()); 991 EXPECT_STREQ("periodic((1), (0)):Bool", GetInductionInfo(x, 0).c_str()); 992 } 993 994 TEST_F(InductionVarAnalysisTest, FindDerivedPeriodicInduction) { 995 // Setup: 996 // k = 0; 997 // for (int i = 0; i < 100; i++) { 998 // t = - k; 999 // k = 1 - k; 1000 // t = k + 100; 1001 // t = k - 100; 1002 // t = k * 100; 1003 // t = k << 1; 1004 // t = - k; 1005 // } 1006 BuildLoopNest(1); 1007 HPhi* k_header = InsertLoopPhi(0, 0); 1008 k_header->AddInput(constant0_); 1009 1010 HInstruction* neg1 = InsertInstruction( 1011 new (GetAllocator()) HNeg(DataType::Type::kInt32, k_header), 0); 1012 HInstruction* idiom = InsertInstruction( 1013 new (GetAllocator()) HSub(DataType::Type::kInt32, constant1_, k_header), 0); 1014 HInstruction* add = InsertInstruction( 1015 new (GetAllocator()) HAdd(DataType::Type::kInt32, idiom, constant100_), 0); 1016 HInstruction* sub = InsertInstruction( 1017 new (GetAllocator()) HSub(DataType::Type::kInt32, idiom, constant100_), 0); 1018 HInstruction* mul = InsertInstruction( 1019 new (GetAllocator()) HMul(DataType::Type::kInt32, idiom, constant100_), 0); 1020 HInstruction* shl = InsertInstruction( 1021 new (GetAllocator()) HShl(DataType::Type::kInt32, idiom, constant1_), 0); 1022 HInstruction* neg2 = InsertInstruction( 1023 new (GetAllocator()) HNeg(DataType::Type::kInt32, idiom), 0); 1024 k_header->AddInput(idiom); 1025 PerformInductionVarAnalysis(); 1026 1027 EXPECT_STREQ("periodic((0), (1)):Int32", GetInductionInfo(k_header, 0).c_str()); 1028 EXPECT_STREQ("periodic((0), ( - (1))):Int32", GetInductionInfo(neg1, 0).c_str()); 1029 EXPECT_STREQ("periodic((1), (0)):Int32", GetInductionInfo(idiom, 0).c_str()); 1030 EXPECT_STREQ("periodic(((1) + (100)), (100)):Int32", GetInductionInfo(add, 0).c_str()); 1031 EXPECT_STREQ("periodic(((1) - (100)), ((0) - (100))):Int32", GetInductionInfo(sub, 0).c_str()); 1032 EXPECT_STREQ("periodic((100), (0)):Int32", GetInductionInfo(mul, 0).c_str()); 1033 EXPECT_STREQ("periodic((2), (0)):Int32", GetInductionInfo(shl, 0).c_str()); 1034 EXPECT_STREQ("periodic(( - (1)), (0)):Int32", GetInductionInfo(neg2, 0).c_str()); 1035 } 1036 1037 TEST_F(InductionVarAnalysisTest, FindDeepLoopInduction) { 1038 // Setup: 1039 // k = 0; 1040 // for (int i_0 = 0; i_0 < 100; i_0++) { 1041 // .. 1042 // for (int i_9 = 0; i_9 < 100; i_9++) { 1043 // k = 1 + k; 1044 // a[k] = 0; 1045 // } 1046 // .. 1047 // } 1048 BuildLoopNest(10); 1049 1050 HPhi* k_header[10]; 1051 for (int d = 0; d < 10; d++) { 1052 k_header[d] = InsertLoopPhi(0, d); 1053 } 1054 1055 HInstruction* inc = InsertInstruction( 1056 new (GetAllocator()) HAdd(DataType::Type::kInt32, constant1_, k_header[9]), 9); 1057 HInstruction* store = InsertArrayStore(inc, 9); 1058 1059 for (int d = 0; d < 10; d++) { 1060 k_header[d]->AddInput((d != 0) ? k_header[d - 1] : constant0_); 1061 k_header[d]->AddInput((d != 9) ? k_header[d + 1] : inc); 1062 } 1063 PerformInductionVarAnalysis(); 1064 1065 // Avoid exact phi number, since that depends on the SSA building phase. 1066 std::regex r("\\(\\(1\\) \\* i \\+ " 1067 "\\(\\(1\\) \\+ \\(\\d+:Phi\\)\\)\\):Int32"); 1068 1069 for (int d = 0; d < 10; d++) { 1070 if (d == 9) { 1071 EXPECT_TRUE(std::regex_match(GetInductionInfo(store->InputAt(1), d), r)); 1072 } else { 1073 EXPECT_STREQ("", GetInductionInfo(store->InputAt(1), d).c_str()); 1074 } 1075 EXPECT_STREQ("((1) * i + (1)):Int32", GetInductionInfo(increment_[d], d).c_str()); 1076 // Trip-count. 1077 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", GetTripCount(d).c_str()); 1078 } 1079 } 1080 1081 TEST_F(InductionVarAnalysisTest, ByteInductionIntLoopControl) { 1082 // Setup: 1083 // for (int i = 0; i < 100; i++) { 1084 // k = (byte) i; 1085 // a[k] = 0; 1086 // a[i] = 0; 1087 // } 1088 BuildLoopNest(1); 1089 HInstruction* conv = InsertInstruction( 1090 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, basic_[0], kNoDexPc), 0); 1091 HInstruction* store1 = InsertArrayStore(conv, 0); 1092 HInstruction* store2 = InsertArrayStore(basic_[0], 0); 1093 PerformInductionVarAnalysis(); 1094 1095 // Regular int induction (i) is transferred over conversion into byte induction (k). 1096 EXPECT_STREQ("((1) * i + (0)):Int8", GetInductionInfo(store1->InputAt(1), 0).c_str()); 1097 EXPECT_STREQ("((1) * i + (0)):Int32", GetInductionInfo(store2->InputAt(1), 0).c_str()); 1098 EXPECT_STREQ("((1) * i + (1)):Int32", GetInductionInfo(increment_[0], 0).c_str()); 1099 1100 // Narrowing detected. 1101 EXPECT_TRUE(IsNarrowingLinear(store1->InputAt(1))); 1102 EXPECT_FALSE(IsNarrowingLinear(store2->InputAt(1))); 1103 1104 // Type matters! 1105 EXPECT_FALSE(HaveSameInduction(store1->InputAt(1), store2->InputAt(1))); 1106 1107 // Trip-count. 1108 EXPECT_STREQ("((100) (TC-loop) ((0) < (100)))", GetTripCount(0).c_str()); 1109 } 1110 1111 TEST_F(InductionVarAnalysisTest, ByteInductionDerivedIntLoopControl) { 1112 // Setup: 1113 // for (int i = 0; i < 100; i++) { 1114 // k = (byte) i; 1115 // a[k] = 0; 1116 // k = k + 1 1117 // a[k] = 0; 1118 // } 1119 BuildLoopNest(1); 1120 HInstruction* conv = InsertInstruction( 1121 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, basic_[0], kNoDexPc), 0); 1122 HInstruction* store1 = InsertArrayStore(conv, 0); 1123 HInstruction* add = InsertInstruction( 1124 new (GetAllocator()) HAdd(DataType::Type::kInt32, conv, constant1_), 0); 1125 HInstruction* store2 = InsertArrayStore(add, 0); 1126 1127 PerformInductionVarAnalysis(); 1128 1129 // Byte induction (k) is detected, but it does not transfer over the addition, 1130 // since this may yield out-of-type values. 1131 EXPECT_STREQ("((1) * i + (0)):Int8", GetInductionInfo(store1->InputAt(1), 0).c_str()); 1132 EXPECT_STREQ("", GetInductionInfo(store2->InputAt(1), 0).c_str()); 1133 1134 // Narrowing detected. 1135 EXPECT_TRUE(IsNarrowingLinear(store1->InputAt(1))); 1136 EXPECT_FALSE(IsNarrowingLinear(store2->InputAt(1))); // works for null 1137 } 1138 1139 TEST_F(InductionVarAnalysisTest, ByteInduction) { 1140 // Setup: 1141 // k = -128; 1142 // for (int i = 0; i < 100; i++) { 1143 // k = k + 1; 1144 // k = (byte) k; 1145 // } 1146 BuildLoopNest(1); 1147 HPhi* k_header = InsertLoopPhi(0, 0); 1148 k_header->AddInput(graph_->GetIntConstant(-128)); 1149 1150 HInstruction* add = InsertInstruction( 1151 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant1_), 0); 1152 HInstruction* conv = InsertInstruction( 1153 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, add, kNoDexPc), 0); 1154 k_header->AddInput(conv); 1155 PerformInductionVarAnalysis(); 1156 1157 // Byte induction (k) is detected, but it does not transfer over the addition, 1158 // since this may yield out-of-type values. 1159 EXPECT_STREQ("((1) * i + (-128)):Int8", GetInductionInfo(k_header, 0).c_str()); 1160 EXPECT_STREQ("", GetInductionInfo(add, 0).c_str()); 1161 1162 // Narrowing detected. 1163 EXPECT_TRUE(IsNarrowingLinear(k_header)); 1164 EXPECT_FALSE(IsNarrowingLinear(add)); // works for null 1165 } 1166 1167 TEST_F(InductionVarAnalysisTest, NoByteInduction1) { 1168 // Setup: 1169 // k = -129; / does not fit! 1170 // for (int i = 0; i < 100; i++) { 1171 // k = k + 1; 1172 // k = (byte) k; 1173 // } 1174 BuildLoopNest(1); 1175 HPhi* k_header = InsertLoopPhi(0, 0); 1176 k_header->AddInput(graph_->GetIntConstant(-129)); 1177 1178 HInstruction* add = InsertInstruction( 1179 new (GetAllocator()) HAdd(DataType::Type::kInt32, k_header, constant1_), 0); 1180 HInstruction* conv = InsertInstruction( 1181 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, add, kNoDexPc), 0); 1182 k_header->AddInput(conv); 1183 PerformInductionVarAnalysis(); 1184 1185 EXPECT_STREQ("", GetInductionInfo(k_header, 0).c_str()); 1186 EXPECT_STREQ("", GetInductionInfo(add, 0).c_str()); 1187 } 1188 1189 TEST_F(InductionVarAnalysisTest, NoByteInduction2) { 1190 // Setup: 1191 // k = 0; 1192 // for (int i = 0; i < 100; i++) { 1193 // k = (byte) k; // conversion not done last! 1194 // k = k + 1; 1195 // } 1196 BuildLoopNest(1); 1197 HPhi* k_header = InsertLoopPhi(0, 0); 1198 k_header->AddInput(constant0_); 1199 1200 HInstruction* conv = InsertInstruction( 1201 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, k_header, kNoDexPc), 0); 1202 HInstruction* add = InsertInstruction( 1203 new (GetAllocator()) HAdd(DataType::Type::kInt32, conv, constant1_), 0); 1204 k_header->AddInput(add); 1205 PerformInductionVarAnalysis(); 1206 1207 EXPECT_STREQ("", GetInductionInfo(k_header, 0).c_str()); 1208 EXPECT_STREQ("", GetInductionInfo(add, 0).c_str()); 1209 } 1210 1211 TEST_F(InductionVarAnalysisTest, ByteLoopControl1) { 1212 // Setup: 1213 // for (byte i = -128; i < 127; i++) { // just fits! 1214 // } 1215 BuildLoopNest(1); 1216 basic_[0]->ReplaceInput(graph_->GetIntConstant(-128), 0); 1217 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 1218 ifs->ReplaceInput(graph_->GetIntConstant(127), 1); 1219 HInstruction* conv = 1220 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, increment_[0], kNoDexPc); 1221 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 1222 basic_[0]->ReplaceInput(conv, 1); 1223 PerformInductionVarAnalysis(); 1224 1225 // Recorded at the phi, but not transferred to increment. 1226 EXPECT_STREQ("((1) * i + (-128)):Int8", GetInductionInfo(basic_[0], 0).c_str()); 1227 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str()); 1228 1229 // Narrowing detected. 1230 EXPECT_TRUE(IsNarrowingLinear(basic_[0])); 1231 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null 1232 1233 // Trip-count. 1234 EXPECT_STREQ("(((127) - (-128)) (TC-loop) ((-128) < (127)))", GetTripCount(0).c_str()); 1235 } 1236 1237 TEST_F(InductionVarAnalysisTest, ByteLoopControl2) { 1238 // Setup: 1239 // for (byte i = -128; i < 128; i++) { // infinite loop! 1240 // } 1241 BuildLoopNest(1); 1242 basic_[0]->ReplaceInput(graph_->GetIntConstant(-128), 0); 1243 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 1244 ifs->ReplaceInput(graph_->GetIntConstant(128), 1); 1245 HInstruction* conv = 1246 new (GetAllocator()) HTypeConversion(DataType::Type::kInt8, increment_[0], kNoDexPc); 1247 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 1248 basic_[0]->ReplaceInput(conv, 1); 1249 PerformInductionVarAnalysis(); 1250 1251 // Recorded at the phi, but not transferred to increment. 1252 EXPECT_STREQ("((1) * i + (-128)):Int8", GetInductionInfo(basic_[0], 0).c_str()); 1253 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str()); 1254 1255 // Narrowing detected. 1256 EXPECT_TRUE(IsNarrowingLinear(basic_[0])); 1257 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null 1258 1259 // Trip-count undefined. 1260 EXPECT_STREQ("", GetTripCount(0).c_str()); 1261 } 1262 1263 TEST_F(InductionVarAnalysisTest, ShortLoopControl1) { 1264 // Setup: 1265 // for (short i = -32768; i < 32767; i++) { // just fits! 1266 // } 1267 BuildLoopNest(1); 1268 basic_[0]->ReplaceInput(graph_->GetIntConstant(-32768), 0); 1269 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 1270 ifs->ReplaceInput(graph_->GetIntConstant(32767), 1); 1271 HInstruction* conv = 1272 new (GetAllocator()) HTypeConversion(DataType::Type::kInt16, increment_[0], kNoDexPc); 1273 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 1274 basic_[0]->ReplaceInput(conv, 1); 1275 PerformInductionVarAnalysis(); 1276 1277 // Recorded at the phi, but not transferred to increment. 1278 EXPECT_STREQ("((1) * i + (-32768)):Int16", GetInductionInfo(basic_[0], 0).c_str()); 1279 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str()); 1280 1281 // Narrowing detected. 1282 EXPECT_TRUE(IsNarrowingLinear(basic_[0])); 1283 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null 1284 1285 // Trip-count. 1286 EXPECT_STREQ("(((32767) - (-32768)) (TC-loop) ((-32768) < (32767)))", GetTripCount(0).c_str()); 1287 } 1288 1289 TEST_F(InductionVarAnalysisTest, ShortLoopControl2) { 1290 // Setup: 1291 // for (short i = -32768; i < 32768; i++) { // infinite loop! 1292 // } 1293 BuildLoopNest(1); 1294 basic_[0]->ReplaceInput(graph_->GetIntConstant(-32768), 0); 1295 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 1296 ifs->ReplaceInput(graph_->GetIntConstant(32768), 1); 1297 HInstruction* conv = 1298 new (GetAllocator()) HTypeConversion(DataType::Type::kInt16, increment_[0], kNoDexPc); 1299 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 1300 basic_[0]->ReplaceInput(conv, 1); 1301 PerformInductionVarAnalysis(); 1302 1303 // Recorded at the phi, but not transferred to increment. 1304 EXPECT_STREQ("((1) * i + (-32768)):Int16", GetInductionInfo(basic_[0], 0).c_str()); 1305 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str()); 1306 1307 // Narrowing detected. 1308 EXPECT_TRUE(IsNarrowingLinear(basic_[0])); 1309 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null 1310 1311 // Trip-count undefined. 1312 EXPECT_STREQ("", GetTripCount(0).c_str()); 1313 } 1314 1315 TEST_F(InductionVarAnalysisTest, CharLoopControl1) { 1316 // Setup: 1317 // for (char i = 0; i < 65535; i++) { // just fits! 1318 // } 1319 BuildLoopNest(1); 1320 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 1321 ifs->ReplaceInput(graph_->GetIntConstant(65535), 1); 1322 HInstruction* conv = 1323 new (GetAllocator()) HTypeConversion(DataType::Type::kUint16, increment_[0], kNoDexPc); 1324 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 1325 basic_[0]->ReplaceInput(conv, 1); 1326 PerformInductionVarAnalysis(); 1327 1328 // Recorded at the phi, but not transferred to increment. 1329 EXPECT_STREQ("((1) * i + (0)):Uint16", GetInductionInfo(basic_[0], 0).c_str()); 1330 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str()); 1331 1332 // Narrowing detected. 1333 EXPECT_TRUE(IsNarrowingLinear(basic_[0])); 1334 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null 1335 1336 // Trip-count. 1337 EXPECT_STREQ("((65535) (TC-loop) ((0) < (65535)))", GetTripCount(0).c_str()); 1338 } 1339 1340 TEST_F(InductionVarAnalysisTest, CharLoopControl2) { 1341 // Setup: 1342 // for (char i = 0; i < 65536; i++) { // infinite loop! 1343 // } 1344 BuildLoopNest(1); 1345 HInstruction* ifs = loop_header_[0]->GetLastInstruction()->GetPrevious(); 1346 ifs->ReplaceInput(graph_->GetIntConstant(65536), 1); 1347 HInstruction* conv = 1348 new (GetAllocator()) HTypeConversion(DataType::Type::kUint16, increment_[0], kNoDexPc); 1349 loop_body_[0]->InsertInstructionBefore(conv, increment_[0]->GetNext()); 1350 basic_[0]->ReplaceInput(conv, 1); 1351 PerformInductionVarAnalysis(); 1352 1353 // Recorded at the phi, but not transferred to increment. 1354 EXPECT_STREQ("((1) * i + (0)):Uint16", GetInductionInfo(basic_[0], 0).c_str()); 1355 EXPECT_STREQ("", GetInductionInfo(increment_[0], 0).c_str()); 1356 1357 // Narrowing detected. 1358 EXPECT_TRUE(IsNarrowingLinear(basic_[0])); 1359 EXPECT_FALSE(IsNarrowingLinear(increment_[0])); // works for null 1360 1361 // Trip-count undefined. 1362 EXPECT_STREQ("", GetTripCount(0).c_str()); 1363 } 1364 1365 } // namespace art 1366
