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 "base/arena_allocator.h" 18 #include "builder.h" 19 #include "induction_var_analysis.h" 20 #include "induction_var_range.h" 21 #include "nodes.h" 22 #include "optimizing_unit_test.h" 23 24 namespace art { 25 26 using Value = InductionVarRange::Value; 27 28 /** 29 * Fixture class for the InductionVarRange tests. 30 */ 31 class InductionVarRangeTest : public CommonCompilerTest { 32 public: 33 InductionVarRangeTest() 34 : pool_(), 35 allocator_(&pool_), 36 graph_(CreateGraph(&allocator_)), 37 iva_(new (&allocator_) HInductionVarAnalysis(graph_)), 38 range_(iva_) { 39 BuildGraph(); 40 } 41 42 ~InductionVarRangeTest() { } 43 44 void ExpectEqual(Value v1, Value v2) { 45 EXPECT_EQ(v1.instruction, v2.instruction); 46 EXPECT_EQ(v1.a_constant, v2.a_constant); 47 EXPECT_EQ(v1.b_constant, v2.b_constant); 48 EXPECT_EQ(v1.is_known, v2.is_known); 49 } 50 51 void ExpectInt(int32_t value, HInstruction* i) { 52 ASSERT_TRUE(i->IsIntConstant()); 53 EXPECT_EQ(value, i->AsIntConstant()->GetValue()); 54 } 55 56 // 57 // Construction methods. 58 // 59 60 /** Constructs bare minimum graph. */ 61 void BuildGraph() { 62 graph_->SetNumberOfVRegs(1); 63 entry_block_ = new (&allocator_) HBasicBlock(graph_); 64 exit_block_ = new (&allocator_) HBasicBlock(graph_); 65 graph_->AddBlock(entry_block_); 66 graph_->AddBlock(exit_block_); 67 graph_->SetEntryBlock(entry_block_); 68 graph_->SetExitBlock(exit_block_); 69 // Two parameters. 70 x_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 71 dex::TypeIndex(0), 72 0, 73 Primitive::kPrimInt); 74 entry_block_->AddInstruction(x_); 75 y_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 76 dex::TypeIndex(0), 77 0, 78 Primitive::kPrimInt); 79 entry_block_->AddInstruction(y_); 80 // Set arbitrary range analysis hint while testing private methods. 81 SetHint(x_); 82 } 83 84 /** Constructs loop with given upper bound. */ 85 void BuildLoop(int32_t lower, HInstruction* upper, int32_t stride) { 86 // Control flow. 87 loop_preheader_ = new (&allocator_) HBasicBlock(graph_); 88 graph_->AddBlock(loop_preheader_); 89 loop_header_ = new (&allocator_) HBasicBlock(graph_); 90 graph_->AddBlock(loop_header_); 91 loop_body_ = new (&allocator_) HBasicBlock(graph_); 92 graph_->AddBlock(loop_body_); 93 HBasicBlock* return_block = new (&allocator_) HBasicBlock(graph_); 94 graph_->AddBlock(return_block); 95 entry_block_->AddSuccessor(loop_preheader_); 96 loop_preheader_->AddSuccessor(loop_header_); 97 loop_header_->AddSuccessor(loop_body_); 98 loop_header_->AddSuccessor(return_block); 99 loop_body_->AddSuccessor(loop_header_); 100 return_block->AddSuccessor(exit_block_); 101 // Instructions. 102 loop_preheader_->AddInstruction(new (&allocator_) HGoto()); 103 HPhi* phi = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt); 104 loop_header_->AddPhi(phi); 105 phi->AddInput(graph_->GetIntConstant(lower)); // i = l 106 if (stride > 0) { 107 condition_ = new (&allocator_) HLessThan(phi, upper); // i < u 108 } else { 109 condition_ = new (&allocator_) HGreaterThan(phi, upper); // i > u 110 } 111 loop_header_->AddInstruction(condition_); 112 loop_header_->AddInstruction(new (&allocator_) HIf(condition_)); 113 increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, phi, graph_->GetIntConstant(stride)); 114 loop_body_->AddInstruction(increment_); // i += s 115 phi->AddInput(increment_); 116 loop_body_->AddInstruction(new (&allocator_) HGoto()); 117 return_block->AddInstruction(new (&allocator_) HReturnVoid()); 118 exit_block_->AddInstruction(new (&allocator_) HExit()); 119 } 120 121 /** Constructs SSA and performs induction variable analysis. */ 122 void PerformInductionVarAnalysis() { 123 graph_->BuildDominatorTree(); 124 iva_->Run(); 125 } 126 127 /** Sets hint. */ 128 void SetHint(HInstruction* hint) { 129 range_.chase_hint_ = hint; 130 } 131 132 /** Constructs an invariant. */ 133 HInductionVarAnalysis::InductionInfo* CreateInvariant(char opc, 134 HInductionVarAnalysis::InductionInfo* a, 135 HInductionVarAnalysis::InductionInfo* b) { 136 HInductionVarAnalysis::InductionOp op; 137 switch (opc) { 138 case '+': op = HInductionVarAnalysis::kAdd; break; 139 case '-': op = HInductionVarAnalysis::kSub; break; 140 case 'n': op = HInductionVarAnalysis::kNeg; break; 141 case '*': op = HInductionVarAnalysis::kMul; break; 142 case '/': op = HInductionVarAnalysis::kDiv; break; 143 case '%': op = HInductionVarAnalysis::kRem; break; 144 case '^': op = HInductionVarAnalysis::kXor; break; 145 case '<': op = HInductionVarAnalysis::kLT; break; 146 default: op = HInductionVarAnalysis::kNop; break; 147 } 148 return iva_->CreateInvariantOp(op, a, b); 149 } 150 151 /** Constructs a fetch. */ 152 HInductionVarAnalysis::InductionInfo* CreateFetch(HInstruction* fetch) { 153 return iva_->CreateInvariantFetch(fetch); 154 } 155 156 /** Constructs a constant. */ 157 HInductionVarAnalysis::InductionInfo* CreateConst(int32_t c) { 158 return CreateFetch(graph_->GetIntConstant(c)); 159 } 160 161 /** Constructs a constant trip-count. */ 162 HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc, bool in_loop, bool safe) { 163 HInductionVarAnalysis::InductionOp op = HInductionVarAnalysis::kTripCountInBodyUnsafe; 164 if (in_loop && safe) { 165 op = HInductionVarAnalysis::kTripCountInLoop; 166 } else if (in_loop) { 167 op = HInductionVarAnalysis::kTripCountInLoopUnsafe; 168 } else if (safe) { 169 op = HInductionVarAnalysis::kTripCountInBody; 170 } 171 // Return TC with taken-test 0 < TC. 172 return iva_->CreateTripCount(op, 173 CreateConst(tc), 174 CreateInvariant('<', CreateConst(0), CreateConst(tc)), 175 Primitive::kPrimInt); 176 } 177 178 /** Constructs a linear a * i + b induction. */ 179 HInductionVarAnalysis::InductionInfo* CreateLinear(int32_t a, int32_t b) { 180 return iva_->CreateInduction(HInductionVarAnalysis::kLinear, 181 HInductionVarAnalysis::kNop, 182 CreateConst(a), 183 CreateConst(b), 184 nullptr, 185 Primitive::kPrimInt); 186 } 187 188 /** Constructs a polynomial sum(a * i + b) + c induction. */ 189 HInductionVarAnalysis::InductionInfo* CreatePolynomial(int32_t a, int32_t b, int32_t c) { 190 return iva_->CreateInduction(HInductionVarAnalysis::kPolynomial, 191 HInductionVarAnalysis::kNop, 192 CreateLinear(a, b), 193 CreateConst(c), 194 nullptr, 195 Primitive::kPrimInt); 196 } 197 198 /** Constructs a geometric a * f^i + b induction. */ 199 HInductionVarAnalysis::InductionInfo* CreateGeometric(int32_t a, int32_t b, int32_t f, char op) { 200 return iva_->CreateInduction(HInductionVarAnalysis::kGeometric, 201 op == '*' ? HInductionVarAnalysis::kMul 202 : HInductionVarAnalysis::kDiv, 203 CreateConst(a), 204 CreateConst(b), 205 graph_->GetIntConstant(f), 206 Primitive::kPrimInt); 207 } 208 209 /** Constructs a range [lo, hi] using a periodic induction. */ 210 HInductionVarAnalysis::InductionInfo* CreateRange(int32_t lo, int32_t hi) { 211 return iva_->CreateInduction(HInductionVarAnalysis::kPeriodic, 212 HInductionVarAnalysis::kNop, 213 CreateConst(lo), 214 CreateConst(hi), 215 nullptr, 216 Primitive::kPrimInt); 217 } 218 219 /** Constructs a wrap-around induction consisting of a constant, followed by info. */ 220 HInductionVarAnalysis::InductionInfo* CreateWrapAround( 221 int32_t initial, 222 HInductionVarAnalysis::InductionInfo* info) { 223 return iva_->CreateInduction(HInductionVarAnalysis::kWrapAround, 224 HInductionVarAnalysis::kNop, 225 CreateConst(initial), 226 info, 227 nullptr, 228 Primitive::kPrimInt); 229 } 230 231 /** Constructs a wrap-around induction consisting of a constant, followed by a range. */ 232 HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) { 233 return CreateWrapAround(initial, CreateRange(lo, hi)); 234 } 235 236 // 237 // Relay methods. 238 // 239 240 bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) { 241 int64_t s = 0; 242 return range_.NeedsTripCount(info, &s); 243 } 244 245 bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) { 246 return range_.IsBodyTripCount(trip); 247 } 248 249 bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) { 250 return range_.IsUnsafeTripCount(trip); 251 } 252 253 Value GetMin(HInductionVarAnalysis::InductionInfo* info, 254 HInductionVarAnalysis::InductionInfo* trip) { 255 return range_.GetVal(info, trip, /* in_body */ true, /* is_min */ true); 256 } 257 258 Value GetMax(HInductionVarAnalysis::InductionInfo* info, 259 HInductionVarAnalysis::InductionInfo* trip) { 260 return range_.GetVal(info, trip, /* in_body */ true, /* is_min */ false); 261 } 262 263 Value GetMul(HInductionVarAnalysis::InductionInfo* info1, 264 HInductionVarAnalysis::InductionInfo* info2, 265 bool is_min) { 266 return range_.GetMul(info1, info2, nullptr, /* in_body */ true, is_min); 267 } 268 269 Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, 270 HInductionVarAnalysis::InductionInfo* info2, 271 bool is_min) { 272 return range_.GetDiv(info1, info2, nullptr, /* in_body */ true, is_min); 273 } 274 275 Value GetRem(HInductionVarAnalysis::InductionInfo* info1, 276 HInductionVarAnalysis::InductionInfo* info2) { 277 return range_.GetRem(info1, info2); 278 } 279 280 Value GetXor(HInductionVarAnalysis::InductionInfo* info1, 281 HInductionVarAnalysis::InductionInfo* info2) { 282 return range_.GetXor(info1, info2); 283 } 284 285 bool IsExact(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { 286 return range_.IsConstant(info, InductionVarRange::kExact, value); 287 } 288 289 bool IsAtMost(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { 290 return range_.IsConstant(info, InductionVarRange::kAtMost, value); 291 } 292 293 bool IsAtLeast(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { 294 return range_.IsConstant(info, InductionVarRange::kAtLeast, value); 295 } 296 297 Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); } 298 Value SubValue(Value v1, Value v2) { return range_.SubValue(v1, v2); } 299 Value MulValue(Value v1, Value v2) { return range_.MulValue(v1, v2); } 300 Value DivValue(Value v1, Value v2) { return range_.DivValue(v1, v2); } 301 Value MinValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, true); } 302 Value MaxValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, false); } 303 304 // General building fields. 305 ArenaPool pool_; 306 ArenaAllocator allocator_; 307 HGraph* graph_; 308 HBasicBlock* entry_block_; 309 HBasicBlock* exit_block_; 310 HBasicBlock* loop_preheader_; 311 HBasicBlock* loop_header_; 312 HBasicBlock* loop_body_; 313 HInductionVarAnalysis* iva_; 314 InductionVarRange range_; 315 316 // Instructions. 317 HInstruction* condition_; 318 HInstruction* increment_; 319 HInstruction* x_; 320 HInstruction* y_; 321 }; 322 323 // 324 // Tests on private methods. 325 // 326 327 TEST_F(InductionVarRangeTest, IsConstant) { 328 int64_t value; 329 // Constant. 330 EXPECT_TRUE(IsExact(CreateConst(12345), &value)); 331 EXPECT_EQ(12345, value); 332 EXPECT_TRUE(IsAtMost(CreateConst(12345), &value)); 333 EXPECT_EQ(12345, value); 334 EXPECT_TRUE(IsAtLeast(CreateConst(12345), &value)); 335 EXPECT_EQ(12345, value); 336 // Constant trivial range. 337 EXPECT_TRUE(IsExact(CreateRange(111, 111), &value)); 338 EXPECT_EQ(111, value); 339 EXPECT_TRUE(IsAtMost(CreateRange(111, 111), &value)); 340 EXPECT_EQ(111, value); 341 EXPECT_TRUE(IsAtLeast(CreateRange(111, 111), &value)); 342 EXPECT_EQ(111, value); 343 // Constant non-trivial range. 344 EXPECT_FALSE(IsExact(CreateRange(11, 22), &value)); 345 EXPECT_TRUE(IsAtMost(CreateRange(11, 22), &value)); 346 EXPECT_EQ(22, value); 347 EXPECT_TRUE(IsAtLeast(CreateRange(11, 22), &value)); 348 EXPECT_EQ(11, value); 349 // Symbolic. 350 EXPECT_FALSE(IsExact(CreateFetch(x_), &value)); 351 EXPECT_FALSE(IsAtMost(CreateFetch(x_), &value)); 352 EXPECT_FALSE(IsAtLeast(CreateFetch(x_), &value)); 353 } 354 355 TEST_F(InductionVarRangeTest, TripCountProperties) { 356 EXPECT_FALSE(NeedsTripCount(nullptr)); 357 EXPECT_FALSE(NeedsTripCount(CreateConst(1))); 358 EXPECT_TRUE(NeedsTripCount(CreateLinear(1, 1))); 359 EXPECT_FALSE(NeedsTripCount(CreateWrapAround(1, 2, 3))); 360 EXPECT_TRUE(NeedsTripCount(CreateWrapAround(1, CreateLinear(1, 1)))); 361 362 EXPECT_FALSE(IsBodyTripCount(nullptr)); 363 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, true))); 364 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, false))); 365 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, true))); 366 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, false))); 367 368 EXPECT_FALSE(IsUnsafeTripCount(nullptr)); 369 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, true, true))); 370 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, true, false))); 371 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, false, true))); 372 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, false, false))); 373 } 374 375 TEST_F(InductionVarRangeTest, GetMinMaxNull) { 376 ExpectEqual(Value(), GetMin(nullptr, nullptr)); 377 ExpectEqual(Value(), GetMax(nullptr, nullptr)); 378 } 379 380 TEST_F(InductionVarRangeTest, GetMinMaxAdd) { 381 ExpectEqual(Value(12), 382 GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); 383 ExpectEqual(Value(22), 384 GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); 385 ExpectEqual(Value(x_, 1, -20), 386 GetMin(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 387 ExpectEqual(Value(x_, 1, -10), 388 GetMax(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 389 ExpectEqual(Value(x_, 1, 10), 390 GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 391 ExpectEqual(Value(x_, 1, 20), 392 GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 393 ExpectEqual(Value(5), 394 GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 395 ExpectEqual(Value(19), 396 GetMax(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 397 } 398 399 TEST_F(InductionVarRangeTest, GetMinMaxSub) { 400 ExpectEqual(Value(-18), 401 GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); 402 ExpectEqual(Value(-8), 403 GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); 404 ExpectEqual(Value(x_, 1, 10), 405 GetMin(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 406 ExpectEqual(Value(x_, 1, 20), 407 GetMax(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 408 ExpectEqual(Value(x_, -1, 10), 409 GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 410 ExpectEqual(Value(x_, -1, 20), 411 GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 412 ExpectEqual(Value(-25), 413 GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 414 ExpectEqual(Value(-11), 415 GetMax(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 416 } 417 418 TEST_F(InductionVarRangeTest, GetMinMaxNeg) { 419 ExpectEqual(Value(-20), GetMin(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); 420 ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); 421 ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); 422 ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); 423 ExpectEqual(Value(x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr)); 424 ExpectEqual(Value(x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr)); 425 } 426 427 TEST_F(InductionVarRangeTest, GetMinMaxMul) { 428 ExpectEqual(Value(20), 429 GetMin(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); 430 ExpectEqual(Value(40), 431 GetMax(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); 432 } 433 434 TEST_F(InductionVarRangeTest, GetMinMaxDiv) { 435 ExpectEqual(Value(3), 436 GetMin(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); 437 ExpectEqual(Value(5), 438 GetMax(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); 439 } 440 441 TEST_F(InductionVarRangeTest, GetMinMaxConstant) { 442 ExpectEqual(Value(12345), GetMin(CreateConst(12345), nullptr)); 443 ExpectEqual(Value(12345), GetMax(CreateConst(12345), nullptr)); 444 } 445 446 TEST_F(InductionVarRangeTest, GetMinMaxFetch) { 447 ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(x_), nullptr)); 448 ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(x_), nullptr)); 449 } 450 451 TEST_F(InductionVarRangeTest, GetMinMaxLinear) { 452 ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100, true, true))); 453 ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100, true, true))); 454 ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100, true, true))); 455 ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100, true, true))); 456 } 457 458 TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) { 459 ExpectEqual(Value(-5), GetMin(CreateWrapAround(-5, -1, 10), nullptr)); 460 ExpectEqual(Value(10), GetMax(CreateWrapAround(-5, -1, 10), nullptr)); 461 ExpectEqual(Value(-1), GetMin(CreateWrapAround(2, -1, 10), nullptr)); 462 ExpectEqual(Value(10), GetMax(CreateWrapAround(2, -1, 10), nullptr)); 463 ExpectEqual(Value(-1), GetMin(CreateWrapAround(20, -1, 10), nullptr)); 464 ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr)); 465 } 466 467 TEST_F(InductionVarRangeTest, GetMinMaxPolynomial) { 468 ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), nullptr)); 469 ExpectEqual(Value(), GetMax(CreatePolynomial(3, 5, 7), nullptr)); 470 ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true))); 471 ExpectEqual(Value(45), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true))); 472 ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true))); 473 ExpectEqual(Value(160), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true))); 474 ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7), 475 CreateTripCount(5, true, true))); 476 ExpectEqual(Value(111), GetMax(CreatePolynomial(11, 13, -7), 477 CreateTripCount(5, true, true))); 478 ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7), 479 CreateTripCount(10, true, true))); 480 ExpectEqual(Value(506), GetMax(CreatePolynomial(11, 13, -7), 481 CreateTripCount(10, true, true))); 482 ExpectEqual(Value(), GetMin(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true))); 483 ExpectEqual(Value(), GetMax(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true))); 484 ExpectEqual(Value(), GetMin(CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true))); 485 ExpectEqual(Value(), GetMax(CreatePolynomial(3, -5, 7), CreateTripCount(10, true, true))); 486 } 487 488 TEST_F(InductionVarRangeTest, GetMinMaxGeometricMul) { 489 ExpectEqual(Value(), GetMin(CreateGeometric(1, 1, 1, '*'), nullptr)); 490 ExpectEqual(Value(), GetMax(CreateGeometric(1, 1, 1, '*'), nullptr)); 491 } 492 493 TEST_F(InductionVarRangeTest, GetMinMaxGeometricDiv) { 494 ExpectEqual(Value(5), GetMin(CreateGeometric(11, 5, 3, '/'), nullptr)); 495 ExpectEqual(Value(16), GetMax(CreateGeometric(11, 5, 3, '/'), nullptr)); 496 ExpectEqual(Value(-5), GetMin(CreateGeometric(11, -5, 3, '/'), nullptr)); 497 ExpectEqual(Value(6), GetMax(CreateGeometric(11, -5, 3, '/'), nullptr)); 498 ExpectEqual(Value(-6), GetMin(CreateGeometric(-11, 5, 3, '/'), nullptr)); 499 ExpectEqual(Value(5), GetMax(CreateGeometric(-11, 5, 3, '/'), nullptr)); 500 ExpectEqual(Value(-16), GetMin(CreateGeometric(-11, -5, 3, '/'), nullptr)); 501 ExpectEqual(Value(-5), GetMax(CreateGeometric(-11, -5, 3, '/'), nullptr)); 502 } 503 504 TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) { 505 ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr)); 506 ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr)); 507 } 508 509 TEST_F(InductionVarRangeTest, GetMulMin) { 510 ExpectEqual(Value(-14), GetMul(CreateConst(2), CreateRange(-7, 8), true)); 511 ExpectEqual(Value(-16), GetMul(CreateConst(-2), CreateRange(-7, 8), true)); 512 ExpectEqual(Value(-14), GetMul(CreateRange(-7, 8), CreateConst(2), true)); 513 ExpectEqual(Value(-16), GetMul(CreateRange(-7, 8), CreateConst(-2), true)); 514 ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true)); 515 ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true)); 516 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), true)); 517 ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true)); 518 ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true)); 519 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), true)); 520 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), true)); 521 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), true)); 522 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), true)); 523 } 524 525 TEST_F(InductionVarRangeTest, GetMulMax) { 526 ExpectEqual(Value(16), GetMul(CreateConst(2), CreateRange(-7, 8), false)); 527 ExpectEqual(Value(14), GetMul(CreateConst(-2), CreateRange(-7, 8), false)); 528 ExpectEqual(Value(16), GetMul(CreateRange(-7, 8), CreateConst(2), false)); 529 ExpectEqual(Value(14), GetMul(CreateRange(-7, 8), CreateConst(-2), false)); 530 ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false)); 531 ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false)); 532 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), false)); 533 ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false)); 534 ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false)); 535 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), false)); 536 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), false)); 537 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), false)); 538 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), false)); 539 } 540 541 TEST_F(InductionVarRangeTest, GetDivMin) { 542 ExpectEqual(Value(-5), GetDiv(CreateRange(-10, 20), CreateConst(2), true)); 543 ExpectEqual(Value(-10), GetDiv(CreateRange(-10, 20), CreateConst(-2), true)); 544 ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true)); 545 ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true)); 546 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), true)); 547 ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true)); 548 ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true)); 549 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), true)); 550 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), true)); 551 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, -40), true)); 552 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), true)); 553 } 554 555 TEST_F(InductionVarRangeTest, GetDivMax) { 556 ExpectEqual(Value(10), GetDiv(CreateRange(-10, 20), CreateConst(2), false)); 557 ExpectEqual(Value(5), GetDiv(CreateRange(-10, 20), CreateConst(-2), false)); 558 ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false)); 559 ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false)); 560 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), false)); 561 ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false)); 562 ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false)); 563 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), false)); 564 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), false)); 565 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, 40), false)); 566 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false)); 567 } 568 569 TEST_F(InductionVarRangeTest, GetMinMaxRem) { 570 ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr)); 571 ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr)); 572 ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr)); 573 ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr)); 574 ExpectEqual(Value(2), GetMin(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr)); 575 ExpectEqual(Value(2), GetMax(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr)); 576 ExpectEqual(Value(1), GetMin(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr)); 577 ExpectEqual(Value(1), GetMax(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr)); 578 } 579 580 TEST_F(InductionVarRangeTest, GetRem) { 581 ExpectEqual(Value(0), GetRem(CreateConst(1), CreateConst(1))); 582 ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(5))); 583 ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(5))); 584 ExpectEqual(Value(-2), GetRem(CreateConst(-2), CreateConst(5))); 585 ExpectEqual(Value(-1), GetRem(CreateConst(-11), CreateConst(5))); 586 ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(-5))); 587 ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(-5))); 588 ExpectEqual(Value(-2), GetRem(CreateConst(-2), CreateConst(-5))); 589 ExpectEqual(Value(-1), GetRem(CreateConst(-11), CreateConst(-5))); 590 ExpectEqual(Value(), GetRem(CreateConst(1), CreateConst(0))); 591 } 592 593 TEST_F(InductionVarRangeTest, GetMinMaxXor) { 594 ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr)); 595 ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr)); 596 ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr)); 597 ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr)); 598 ExpectEqual(Value(3), GetMin(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr)); 599 ExpectEqual(Value(3), GetMax(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr)); 600 } 601 602 TEST_F(InductionVarRangeTest, GetXor) { 603 ExpectEqual(Value(0), GetXor(CreateConst(1), CreateConst(1))); 604 ExpectEqual(Value(3), GetXor(CreateConst(1), CreateConst(2))); 605 ExpectEqual(Value(-2), GetXor(CreateConst(1), CreateConst(-1))); 606 ExpectEqual(Value(0), GetXor(CreateConst(-1), CreateConst(-1))); 607 } 608 609 TEST_F(InductionVarRangeTest, AddValue) { 610 ExpectEqual(Value(110), AddValue(Value(10), Value(100))); 611 ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1))); 612 ExpectEqual(Value(x_, 3, -5), AddValue(Value(x_, 2, -4), Value(x_, 1, -1))); 613 ExpectEqual(Value(), AddValue(Value(x_, 1, 5), Value(y_, 1, -7))); 614 ExpectEqual(Value(x_, 1, 23), AddValue(Value(x_, 1, 20), Value(3))); 615 ExpectEqual(Value(y_, 1, 5), AddValue(Value(55), Value(y_, 1, -50))); 616 const int32_t max_value = std::numeric_limits<int32_t>::max(); 617 ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5))); 618 ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe 619 } 620 621 TEST_F(InductionVarRangeTest, SubValue) { 622 ExpectEqual(Value(-90), SubValue(Value(10), Value(100))); 623 ExpectEqual(Value(-3), SubValue(Value(x_, 1, -4), Value(x_, 1, -1))); 624 ExpectEqual(Value(x_, 2, -3), SubValue(Value(x_, 3, -4), Value(x_, 1, -1))); 625 ExpectEqual(Value(), SubValue(Value(x_, 1, 5), Value(y_, 1, -7))); 626 ExpectEqual(Value(x_, 1, 17), SubValue(Value(x_, 1, 20), Value(3))); 627 ExpectEqual(Value(y_, -4, 105), SubValue(Value(55), Value(y_, 4, -50))); 628 const int32_t min_value = std::numeric_limits<int32_t>::min(); 629 ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5))); 630 ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe 631 } 632 633 TEST_F(InductionVarRangeTest, MulValue) { 634 ExpectEqual(Value(1000), MulValue(Value(10), Value(100))); 635 ExpectEqual(Value(), MulValue(Value(x_, 1, -4), Value(x_, 1, -1))); 636 ExpectEqual(Value(), MulValue(Value(x_, 1, 5), Value(y_, 1, -7))); 637 ExpectEqual(Value(x_, 9, 60), MulValue(Value(x_, 3, 20), Value(3))); 638 ExpectEqual(Value(y_, 55, -110), MulValue(Value(55), Value(y_, 1, -2))); 639 ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe 640 } 641 642 TEST_F(InductionVarRangeTest, MulValueSpecial) { 643 const int32_t min_value = std::numeric_limits<int32_t>::min(); 644 const int32_t max_value = std::numeric_limits<int32_t>::max(); 645 646 // Unsafe. 647 ExpectEqual(Value(), MulValue(Value(min_value), Value(min_value))); 648 ExpectEqual(Value(), MulValue(Value(min_value), Value(-1))); 649 ExpectEqual(Value(), MulValue(Value(min_value), Value(max_value))); 650 ExpectEqual(Value(), MulValue(Value(max_value), Value(max_value))); 651 652 // Safe. 653 ExpectEqual(Value(min_value), MulValue(Value(min_value), Value(1))); 654 ExpectEqual(Value(max_value), MulValue(Value(max_value), Value(1))); 655 ExpectEqual(Value(-max_value), MulValue(Value(max_value), Value(-1))); 656 ExpectEqual(Value(-1), MulValue(Value(1), Value(-1))); 657 ExpectEqual(Value(1), MulValue(Value(-1), Value(-1))); 658 } 659 660 TEST_F(InductionVarRangeTest, DivValue) { 661 ExpectEqual(Value(25), DivValue(Value(100), Value(4))); 662 ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1))); 663 ExpectEqual(Value(), DivValue(Value(x_, 1, 5), Value(y_, 1, -7))); 664 ExpectEqual(Value(), DivValue(Value(x_, 12, 24), Value(3))); 665 ExpectEqual(Value(), DivValue(Value(55), Value(y_, 1, -50))); 666 ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe 667 } 668 669 TEST_F(InductionVarRangeTest, DivValueSpecial) { 670 const int32_t min_value = std::numeric_limits<int32_t>::min(); 671 const int32_t max_value = std::numeric_limits<int32_t>::max(); 672 673 // Unsafe. 674 ExpectEqual(Value(), DivValue(Value(min_value), Value(-1))); 675 676 // Safe. 677 ExpectEqual(Value(1), DivValue(Value(min_value), Value(min_value))); 678 ExpectEqual(Value(1), DivValue(Value(max_value), Value(max_value))); 679 ExpectEqual(Value(min_value), DivValue(Value(min_value), Value(1))); 680 ExpectEqual(Value(max_value), DivValue(Value(max_value), Value(1))); 681 ExpectEqual(Value(-max_value), DivValue(Value(max_value), Value(-1))); 682 ExpectEqual(Value(-1), DivValue(Value(1), Value(-1))); 683 ExpectEqual(Value(1), DivValue(Value(-1), Value(-1))); 684 } 685 686 TEST_F(InductionVarRangeTest, MinValue) { 687 ExpectEqual(Value(10), MinValue(Value(10), Value(100))); 688 ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1))); 689 ExpectEqual(Value(x_, 4, -4), MinValue(Value(x_, 4, -4), Value(x_, 4, -1))); 690 ExpectEqual(Value(), MinValue(Value(x_, 1, 5), Value(y_, 1, -7))); 691 ExpectEqual(Value(), MinValue(Value(x_, 1, 20), Value(3))); 692 ExpectEqual(Value(), MinValue(Value(55), Value(y_, 1, -50))); 693 } 694 695 TEST_F(InductionVarRangeTest, MaxValue) { 696 ExpectEqual(Value(100), MaxValue(Value(10), Value(100))); 697 ExpectEqual(Value(x_, 1, -1), MaxValue(Value(x_, 1, -4), Value(x_, 1, -1))); 698 ExpectEqual(Value(x_, 4, -1), MaxValue(Value(x_, 4, -4), Value(x_, 4, -1))); 699 ExpectEqual(Value(), MaxValue(Value(x_, 1, 5), Value(y_, 1, -7))); 700 ExpectEqual(Value(), MaxValue(Value(x_, 1, 20), Value(3))); 701 ExpectEqual(Value(), MaxValue(Value(55), Value(y_, 1, -50))); 702 } 703 704 TEST_F(InductionVarRangeTest, ArrayLengthAndHints) { 705 // We pass a bogus constant for the class to avoid mocking one. 706 HInstruction* new_array = new (&allocator_) HNewArray(x_, x_, 0); 707 entry_block_->AddInstruction(new_array); 708 HInstruction* array_length = new (&allocator_) HArrayLength(new_array, 0); 709 entry_block_->AddInstruction(array_length); 710 // With null hint: yields extreme constants. 711 const int32_t max_value = std::numeric_limits<int32_t>::max(); 712 SetHint(nullptr); 713 ExpectEqual(Value(0), GetMin(CreateFetch(array_length), nullptr)); 714 ExpectEqual(Value(max_value), GetMax(CreateFetch(array_length), nullptr)); 715 // With explicit hint: yields the length instruction. 716 SetHint(array_length); 717 ExpectEqual(Value(array_length, 1, 0), GetMin(CreateFetch(array_length), nullptr)); 718 ExpectEqual(Value(array_length, 1, 0), GetMax(CreateFetch(array_length), nullptr)); 719 // With any non-null hint: chases beyond the length instruction. 720 SetHint(x_); 721 ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(array_length), nullptr)); 722 ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(array_length), nullptr)); 723 } 724 725 // 726 // Tests on public methods. 727 // 728 729 TEST_F(InductionVarRangeTest, ConstantTripCountUp) { 730 BuildLoop(0, graph_->GetIntConstant(1000), 1); 731 PerformInductionVarAnalysis(); 732 733 Value v1, v2; 734 bool needs_finite_test = true; 735 bool needs_taken_test = true; 736 737 HInstruction* phi = condition_->InputAt(0); 738 HInstruction* exit = exit_block_->GetLastInstruction(); 739 740 // In context of header: known. 741 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); 742 EXPECT_FALSE(needs_finite_test); 743 ExpectEqual(Value(0), v1); 744 ExpectEqual(Value(1000), v2); 745 746 // In context of loop-body: known. 747 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); 748 EXPECT_FALSE(needs_finite_test); 749 ExpectEqual(Value(0), v1); 750 ExpectEqual(Value(999), v2); 751 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 752 EXPECT_FALSE(needs_finite_test); 753 ExpectEqual(Value(1), v1); 754 ExpectEqual(Value(1000), v2); 755 756 // Induction vs. no-induction. 757 EXPECT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); 758 EXPECT_TRUE(range_.CanGenerateLastValue(phi)); 759 EXPECT_FALSE(range_.CanGenerateRange(exit, exit, &needs_finite_test, &needs_taken_test)); 760 EXPECT_FALSE(range_.CanGenerateLastValue(exit)); 761 762 // Last value (unsimplified). 763 HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_); 764 ASSERT_TRUE(last->IsAdd()); 765 ExpectInt(1000, last->InputAt(0)); 766 ExpectInt(0, last->InputAt(1)); 767 768 // Loop logic. 769 int64_t tc = 0; 770 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc)); 771 EXPECT_EQ(1000, tc); 772 HInstruction* offset = nullptr; 773 EXPECT_TRUE(range_.IsUnitStride(phi, phi, graph_, &offset)); 774 ExpectInt(0, offset); 775 HInstruction* tce = range_.GenerateTripCount( 776 loop_header_->GetLoopInformation(), graph_, loop_preheader_); 777 ASSERT_TRUE(tce != nullptr); 778 ExpectInt(1000, tce); 779 } 780 781 TEST_F(InductionVarRangeTest, ConstantTripCountDown) { 782 BuildLoop(1000, graph_->GetIntConstant(0), -1); 783 PerformInductionVarAnalysis(); 784 785 Value v1, v2; 786 bool needs_finite_test = true; 787 bool needs_taken_test = true; 788 789 HInstruction* phi = condition_->InputAt(0); 790 HInstruction* exit = exit_block_->GetLastInstruction(); 791 792 // In context of header: known. 793 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); 794 EXPECT_FALSE(needs_finite_test); 795 ExpectEqual(Value(0), v1); 796 ExpectEqual(Value(1000), v2); 797 798 // In context of loop-body: known. 799 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); 800 EXPECT_FALSE(needs_finite_test); 801 ExpectEqual(Value(1), v1); 802 ExpectEqual(Value(1000), v2); 803 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 804 EXPECT_FALSE(needs_finite_test); 805 ExpectEqual(Value(0), v1); 806 ExpectEqual(Value(999), v2); 807 808 // Induction vs. no-induction. 809 EXPECT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); 810 EXPECT_TRUE(range_.CanGenerateLastValue(phi)); 811 EXPECT_FALSE(range_.CanGenerateRange(exit, exit, &needs_finite_test, &needs_taken_test)); 812 EXPECT_FALSE(range_.CanGenerateLastValue(exit)); 813 814 // Last value (unsimplified). 815 HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_); 816 ASSERT_TRUE(last->IsSub()); 817 ExpectInt(1000, last->InputAt(0)); 818 ASSERT_TRUE(last->InputAt(1)->IsNeg()); 819 last = last->InputAt(1)->InputAt(0); 820 ASSERT_TRUE(last->IsSub()); 821 ExpectInt(0, last->InputAt(0)); 822 ExpectInt(1000, last->InputAt(1)); 823 824 // Loop logic. 825 int64_t tc = 0; 826 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc)); 827 EXPECT_EQ(1000, tc); 828 HInstruction* offset = nullptr; 829 EXPECT_FALSE(range_.IsUnitStride(phi, phi, graph_, &offset)); 830 HInstruction* tce = range_.GenerateTripCount( 831 loop_header_->GetLoopInformation(), graph_, loop_preheader_); 832 ASSERT_TRUE(tce != nullptr); 833 ASSERT_TRUE(tce->IsNeg()); 834 last = tce->InputAt(0); 835 EXPECT_TRUE(last->IsSub()); 836 ExpectInt(0, last->InputAt(0)); 837 ExpectInt(1000, last->InputAt(1)); 838 } 839 840 TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { 841 BuildLoop(0, x_, 1); 842 PerformInductionVarAnalysis(); 843 844 Value v1, v2; 845 bool needs_finite_test = true; 846 bool needs_taken_test = true; 847 848 HInstruction* phi = condition_->InputAt(0); 849 850 // In context of header: upper unknown. 851 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); 852 EXPECT_FALSE(needs_finite_test); 853 ExpectEqual(Value(0), v1); 854 ExpectEqual(Value(), v2); 855 856 // In context of loop-body: known. 857 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); 858 EXPECT_FALSE(needs_finite_test); 859 ExpectEqual(Value(0), v1); 860 ExpectEqual(Value(x_, 1, -1), v2); 861 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 862 EXPECT_FALSE(needs_finite_test); 863 ExpectEqual(Value(1), v1); 864 ExpectEqual(Value(x_, 1, 0), v2); 865 866 HInstruction* lower = nullptr; 867 HInstruction* upper = nullptr; 868 869 // Can generate code in context of loop-body only. 870 EXPECT_FALSE(range_.CanGenerateRange(condition_, phi, &needs_finite_test, &needs_taken_test)); 871 ASSERT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); 872 EXPECT_FALSE(needs_finite_test); 873 EXPECT_TRUE(needs_taken_test); 874 875 // Generates code (unsimplified). 876 range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper); 877 878 // Verify lower is 0+0. 879 ASSERT_TRUE(lower != nullptr); 880 ASSERT_TRUE(lower->IsAdd()); 881 ExpectInt(0, lower->InputAt(0)); 882 ExpectInt(0, lower->InputAt(1)); 883 884 // Verify upper is (V-1)+0. 885 ASSERT_TRUE(upper != nullptr); 886 ASSERT_TRUE(upper->IsAdd()); 887 ASSERT_TRUE(upper->InputAt(0)->IsSub()); 888 EXPECT_TRUE(upper->InputAt(0)->InputAt(0)->IsParameterValue()); 889 ExpectInt(1, upper->InputAt(0)->InputAt(1)); 890 ExpectInt(0, upper->InputAt(1)); 891 892 // Verify taken-test is 0<V. 893 HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_); 894 ASSERT_TRUE(taken != nullptr); 895 ASSERT_TRUE(taken->IsLessThan()); 896 ExpectInt(0, taken->InputAt(0)); 897 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); 898 899 // Replacement. 900 range_.Replace(loop_header_->GetLastInstruction(), x_, y_); 901 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 902 EXPECT_FALSE(needs_finite_test); 903 ExpectEqual(Value(1), v1); 904 ExpectEqual(Value(y_, 1, 0), v2); 905 906 // Loop logic. 907 int64_t tc = 0; 908 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc)); 909 EXPECT_EQ(0, tc); // unknown 910 HInstruction* offset = nullptr; 911 EXPECT_TRUE(range_.IsUnitStride(phi, phi, graph_, &offset)); 912 ExpectInt(0, offset); 913 HInstruction* tce = range_.GenerateTripCount( 914 loop_header_->GetLoopInformation(), graph_, loop_preheader_); 915 ASSERT_TRUE(tce != nullptr); 916 EXPECT_TRUE(tce->IsSelect()); // guarded by taken-test 917 ExpectInt(0, tce->InputAt(0)); 918 EXPECT_TRUE(tce->InputAt(1)->IsParameterValue()); 919 EXPECT_TRUE(tce->InputAt(2)->IsLessThan()); 920 } 921 922 TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { 923 BuildLoop(1000, x_, -1); 924 PerformInductionVarAnalysis(); 925 926 Value v1, v2; 927 bool needs_finite_test = true; 928 bool needs_taken_test = true; 929 930 HInstruction* phi = condition_->InputAt(0); 931 932 // In context of header: lower unknown. 933 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); 934 EXPECT_FALSE(needs_finite_test); 935 ExpectEqual(Value(), v1); 936 ExpectEqual(Value(1000), v2); 937 938 // In context of loop-body: known. 939 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); 940 EXPECT_FALSE(needs_finite_test); 941 ExpectEqual(Value(x_, 1, 1), v1); 942 ExpectEqual(Value(1000), v2); 943 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 944 EXPECT_FALSE(needs_finite_test); 945 ExpectEqual(Value(x_, 1, 0), v1); 946 ExpectEqual(Value(999), v2); 947 948 HInstruction* lower = nullptr; 949 HInstruction* upper = nullptr; 950 951 // Can generate code in context of loop-body only. 952 EXPECT_FALSE(range_.CanGenerateRange(condition_, phi, &needs_finite_test, &needs_taken_test)); 953 ASSERT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); 954 EXPECT_FALSE(needs_finite_test); 955 EXPECT_TRUE(needs_taken_test); 956 957 // Generates code (unsimplified). 958 range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper); 959 960 // Verify lower is 1000-((1000-V)-1). 961 ASSERT_TRUE(lower != nullptr); 962 ASSERT_TRUE(lower->IsSub()); 963 ExpectInt(1000, lower->InputAt(0)); 964 lower = lower->InputAt(1); 965 ASSERT_TRUE(lower->IsSub()); 966 ExpectInt(1, lower->InputAt(1)); 967 lower = lower->InputAt(0); 968 ASSERT_TRUE(lower->IsSub()); 969 ExpectInt(1000, lower->InputAt(0)); 970 EXPECT_TRUE(lower->InputAt(1)->IsParameterValue()); 971 972 // Verify upper is 1000-0. 973 ASSERT_TRUE(upper != nullptr); 974 ASSERT_TRUE(upper->IsSub()); 975 ExpectInt(1000, upper->InputAt(0)); 976 ExpectInt(0, upper->InputAt(1)); 977 978 // Verify taken-test is 1000>V. 979 HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_); 980 ASSERT_TRUE(taken != nullptr); 981 ASSERT_TRUE(taken->IsGreaterThan()); 982 ExpectInt(1000, taken->InputAt(0)); 983 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); 984 985 // Replacement. 986 range_.Replace(loop_header_->GetLastInstruction(), x_, y_); 987 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 988 EXPECT_FALSE(needs_finite_test); 989 ExpectEqual(Value(y_, 1, 0), v1); 990 ExpectEqual(Value(999), v2); 991 992 // Loop logic. 993 int64_t tc = 0; 994 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc)); 995 EXPECT_EQ(0, tc); // unknown 996 HInstruction* offset = nullptr; 997 EXPECT_FALSE(range_.IsUnitStride(phi, phi, graph_, &offset)); 998 HInstruction* tce = range_.GenerateTripCount( 999 loop_header_->GetLoopInformation(), graph_, loop_preheader_); 1000 ASSERT_TRUE(tce != nullptr); 1001 EXPECT_TRUE(tce->IsSelect()); // guarded by taken-test 1002 ExpectInt(0, tce->InputAt(0)); 1003 EXPECT_TRUE(tce->InputAt(1)->IsSub()); 1004 EXPECT_TRUE(tce->InputAt(2)->IsGreaterThan()); 1005 tce = tce->InputAt(1); 1006 ExpectInt(1000, taken->InputAt(0)); 1007 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); 1008 } 1009 1010 } // namespace art 1011
