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 "induction_var_range.h" 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 using Value = InductionVarRange::Value; 28 29 /** 30 * Fixture class for the InductionVarRange tests. 31 */ 32 class InductionVarRangeTest : public OptimizingUnitTest { 33 public: 34 InductionVarRangeTest() 35 : graph_(CreateGraph()), 36 iva_(new (GetAllocator()) HInductionVarAnalysis(graph_)), 37 range_(iva_) { 38 BuildGraph(); 39 } 40 41 ~InductionVarRangeTest() { } 42 43 void ExpectEqual(Value v1, Value v2) { 44 EXPECT_EQ(v1.instruction, v2.instruction); 45 EXPECT_EQ(v1.a_constant, v2.a_constant); 46 EXPECT_EQ(v1.b_constant, v2.b_constant); 47 EXPECT_EQ(v1.is_known, v2.is_known); 48 } 49 50 void ExpectInt(int32_t value, HInstruction* i) { 51 ASSERT_TRUE(i->IsIntConstant()); 52 EXPECT_EQ(value, i->AsIntConstant()->GetValue()); 53 } 54 55 // 56 // Construction methods. 57 // 58 59 /** Constructs bare minimum graph. */ 60 void BuildGraph() { 61 graph_->SetNumberOfVRegs(1); 62 entry_block_ = new (GetAllocator()) HBasicBlock(graph_); 63 exit_block_ = new (GetAllocator()) HBasicBlock(graph_); 64 graph_->AddBlock(entry_block_); 65 graph_->AddBlock(exit_block_); 66 graph_->SetEntryBlock(entry_block_); 67 graph_->SetExitBlock(exit_block_); 68 // Two parameters. 69 x_ = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 70 dex::TypeIndex(0), 71 0, 72 DataType::Type::kInt32); 73 entry_block_->AddInstruction(x_); 74 y_ = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 75 dex::TypeIndex(0), 76 0, 77 DataType::Type::kInt32); 78 entry_block_->AddInstruction(y_); 79 // Set arbitrary range analysis hint while testing private methods. 80 SetHint(x_); 81 } 82 83 /** Constructs loop with given upper bound. */ 84 void BuildLoop(int32_t lower, HInstruction* upper, int32_t stride) { 85 // Control flow. 86 loop_preheader_ = new (GetAllocator()) HBasicBlock(graph_); 87 graph_->AddBlock(loop_preheader_); 88 loop_header_ = new (GetAllocator()) HBasicBlock(graph_); 89 graph_->AddBlock(loop_header_); 90 loop_body_ = new (GetAllocator()) HBasicBlock(graph_); 91 graph_->AddBlock(loop_body_); 92 HBasicBlock* return_block = new (GetAllocator()) HBasicBlock(graph_); 93 graph_->AddBlock(return_block); 94 entry_block_->AddSuccessor(loop_preheader_); 95 loop_preheader_->AddSuccessor(loop_header_); 96 loop_header_->AddSuccessor(loop_body_); 97 loop_header_->AddSuccessor(return_block); 98 loop_body_->AddSuccessor(loop_header_); 99 return_block->AddSuccessor(exit_block_); 100 // Instructions. 101 loop_preheader_->AddInstruction(new (GetAllocator()) HGoto()); 102 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32); 103 loop_header_->AddPhi(phi); 104 phi->AddInput(graph_->GetIntConstant(lower)); // i = l 105 if (stride > 0) { 106 condition_ = new (GetAllocator()) HLessThan(phi, upper); // i < u 107 } else { 108 condition_ = new (GetAllocator()) HGreaterThan(phi, upper); // i > u 109 } 110 loop_header_->AddInstruction(condition_); 111 loop_header_->AddInstruction(new (GetAllocator()) HIf(condition_)); 112 increment_ = 113 new (GetAllocator()) HAdd(DataType::Type::kInt32, phi, graph_->GetIntConstant(stride)); 114 loop_body_->AddInstruction(increment_); // i += s 115 phi->AddInput(increment_); 116 loop_body_->AddInstruction(new (GetAllocator()) HGoto()); 117 return_block->AddInstruction(new (GetAllocator()) HReturnVoid()); 118 exit_block_->AddInstruction(new (GetAllocator()) 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 DataType::Type::kInt32); 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 DataType::Type::kInt32); 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 DataType::Type::kInt32); 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 DataType::Type::kInt32); 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 DataType::Type::kInt32); 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 DataType::Type::kInt32); 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 HGraph* graph_; 306 HBasicBlock* entry_block_; 307 HBasicBlock* exit_block_; 308 HBasicBlock* loop_preheader_; 309 HBasicBlock* loop_header_; 310 HBasicBlock* loop_body_; 311 HInductionVarAnalysis* iva_; 312 InductionVarRange range_; 313 314 // Instructions. 315 HInstruction* condition_; 316 HInstruction* increment_; 317 HInstruction* x_; 318 HInstruction* y_; 319 }; 320 321 // 322 // Tests on private methods. 323 // 324 325 TEST_F(InductionVarRangeTest, IsConstant) { 326 int64_t value; 327 // Constant. 328 EXPECT_TRUE(IsExact(CreateConst(12345), &value)); 329 EXPECT_EQ(12345, value); 330 EXPECT_TRUE(IsAtMost(CreateConst(12345), &value)); 331 EXPECT_EQ(12345, value); 332 EXPECT_TRUE(IsAtLeast(CreateConst(12345), &value)); 333 EXPECT_EQ(12345, value); 334 // Constant trivial range. 335 EXPECT_TRUE(IsExact(CreateRange(111, 111), &value)); 336 EXPECT_EQ(111, value); 337 EXPECT_TRUE(IsAtMost(CreateRange(111, 111), &value)); 338 EXPECT_EQ(111, value); 339 EXPECT_TRUE(IsAtLeast(CreateRange(111, 111), &value)); 340 EXPECT_EQ(111, value); 341 // Constant non-trivial range. 342 EXPECT_FALSE(IsExact(CreateRange(11, 22), &value)); 343 EXPECT_TRUE(IsAtMost(CreateRange(11, 22), &value)); 344 EXPECT_EQ(22, value); 345 EXPECT_TRUE(IsAtLeast(CreateRange(11, 22), &value)); 346 EXPECT_EQ(11, value); 347 // Symbolic. 348 EXPECT_FALSE(IsExact(CreateFetch(x_), &value)); 349 EXPECT_FALSE(IsAtMost(CreateFetch(x_), &value)); 350 EXPECT_FALSE(IsAtLeast(CreateFetch(x_), &value)); 351 } 352 353 TEST_F(InductionVarRangeTest, TripCountProperties) { 354 EXPECT_FALSE(NeedsTripCount(nullptr)); 355 EXPECT_FALSE(NeedsTripCount(CreateConst(1))); 356 EXPECT_TRUE(NeedsTripCount(CreateLinear(1, 1))); 357 EXPECT_FALSE(NeedsTripCount(CreateWrapAround(1, 2, 3))); 358 EXPECT_TRUE(NeedsTripCount(CreateWrapAround(1, CreateLinear(1, 1)))); 359 360 EXPECT_FALSE(IsBodyTripCount(nullptr)); 361 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, true))); 362 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, false))); 363 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, true))); 364 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, false))); 365 366 EXPECT_FALSE(IsUnsafeTripCount(nullptr)); 367 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, true, true))); 368 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, true, false))); 369 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, false, true))); 370 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, false, false))); 371 } 372 373 TEST_F(InductionVarRangeTest, GetMinMaxNull) { 374 ExpectEqual(Value(), GetMin(nullptr, nullptr)); 375 ExpectEqual(Value(), GetMax(nullptr, nullptr)); 376 } 377 378 TEST_F(InductionVarRangeTest, GetMinMaxAdd) { 379 ExpectEqual(Value(12), 380 GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); 381 ExpectEqual(Value(22), 382 GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); 383 ExpectEqual(Value(x_, 1, -20), 384 GetMin(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 385 ExpectEqual(Value(x_, 1, -10), 386 GetMax(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 387 ExpectEqual(Value(x_, 1, 10), 388 GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 389 ExpectEqual(Value(x_, 1, 20), 390 GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 391 ExpectEqual(Value(5), 392 GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 393 ExpectEqual(Value(19), 394 GetMax(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 395 } 396 397 TEST_F(InductionVarRangeTest, GetMinMaxSub) { 398 ExpectEqual(Value(-18), 399 GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); 400 ExpectEqual(Value(-8), 401 GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); 402 ExpectEqual(Value(x_, 1, 10), 403 GetMin(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 404 ExpectEqual(Value(x_, 1, 20), 405 GetMax(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 406 ExpectEqual(Value(x_, -1, 10), 407 GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 408 ExpectEqual(Value(x_, -1, 20), 409 GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 410 ExpectEqual(Value(-25), 411 GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 412 ExpectEqual(Value(-11), 413 GetMax(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 414 } 415 416 TEST_F(InductionVarRangeTest, GetMinMaxNeg) { 417 ExpectEqual(Value(-20), GetMin(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); 418 ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); 419 ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); 420 ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); 421 ExpectEqual(Value(x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr)); 422 ExpectEqual(Value(x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr)); 423 } 424 425 TEST_F(InductionVarRangeTest, GetMinMaxMul) { 426 ExpectEqual(Value(20), 427 GetMin(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); 428 ExpectEqual(Value(40), 429 GetMax(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); 430 } 431 432 TEST_F(InductionVarRangeTest, GetMinMaxDiv) { 433 ExpectEqual(Value(3), 434 GetMin(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); 435 ExpectEqual(Value(5), 436 GetMax(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); 437 } 438 439 TEST_F(InductionVarRangeTest, GetMinMaxConstant) { 440 ExpectEqual(Value(12345), GetMin(CreateConst(12345), nullptr)); 441 ExpectEqual(Value(12345), GetMax(CreateConst(12345), nullptr)); 442 } 443 444 TEST_F(InductionVarRangeTest, GetMinMaxFetch) { 445 ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(x_), nullptr)); 446 ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(x_), nullptr)); 447 } 448 449 TEST_F(InductionVarRangeTest, GetMinMaxLinear) { 450 ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100, true, true))); 451 ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100, true, true))); 452 ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100, true, true))); 453 ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100, true, true))); 454 } 455 456 TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) { 457 ExpectEqual(Value(-5), GetMin(CreateWrapAround(-5, -1, 10), nullptr)); 458 ExpectEqual(Value(10), GetMax(CreateWrapAround(-5, -1, 10), nullptr)); 459 ExpectEqual(Value(-1), GetMin(CreateWrapAround(2, -1, 10), nullptr)); 460 ExpectEqual(Value(10), GetMax(CreateWrapAround(2, -1, 10), nullptr)); 461 ExpectEqual(Value(-1), GetMin(CreateWrapAround(20, -1, 10), nullptr)); 462 ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr)); 463 } 464 465 TEST_F(InductionVarRangeTest, GetMinMaxPolynomial) { 466 ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), nullptr)); 467 ExpectEqual(Value(), GetMax(CreatePolynomial(3, 5, 7), nullptr)); 468 ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true))); 469 ExpectEqual(Value(45), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(5, true, true))); 470 ExpectEqual(Value(7), GetMin(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true))); 471 ExpectEqual(Value(160), GetMax(CreatePolynomial(3, 5, 7), CreateTripCount(10, true, true))); 472 ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7), 473 CreateTripCount(5, true, true))); 474 ExpectEqual(Value(111), GetMax(CreatePolynomial(11, 13, -7), 475 CreateTripCount(5, true, true))); 476 ExpectEqual(Value(-7), GetMin(CreatePolynomial(11, 13, -7), 477 CreateTripCount(10, true, true))); 478 ExpectEqual(Value(506), GetMax(CreatePolynomial(11, 13, -7), 479 CreateTripCount(10, true, true))); 480 ExpectEqual(Value(), GetMin(CreatePolynomial(-3, 5, 7), CreateTripCount(10, true, true))); 481 ExpectEqual(Value(), GetMax(CreatePolynomial(-3, 5, 7), 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 } 485 486 TEST_F(InductionVarRangeTest, GetMinMaxGeometricMul) { 487 ExpectEqual(Value(), GetMin(CreateGeometric(1, 1, 1, '*'), nullptr)); 488 ExpectEqual(Value(), GetMax(CreateGeometric(1, 1, 1, '*'), nullptr)); 489 } 490 491 TEST_F(InductionVarRangeTest, GetMinMaxGeometricDiv) { 492 ExpectEqual(Value(5), GetMin(CreateGeometric(11, 5, 3, '/'), nullptr)); 493 ExpectEqual(Value(16), GetMax(CreateGeometric(11, 5, 3, '/'), nullptr)); 494 ExpectEqual(Value(-5), GetMin(CreateGeometric(11, -5, 3, '/'), nullptr)); 495 ExpectEqual(Value(6), GetMax(CreateGeometric(11, -5, 3, '/'), nullptr)); 496 ExpectEqual(Value(-6), GetMin(CreateGeometric(-11, 5, 3, '/'), nullptr)); 497 ExpectEqual(Value(5), GetMax(CreateGeometric(-11, 5, 3, '/'), nullptr)); 498 ExpectEqual(Value(-16), GetMin(CreateGeometric(-11, -5, 3, '/'), nullptr)); 499 ExpectEqual(Value(-5), GetMax(CreateGeometric(-11, -5, 3, '/'), nullptr)); 500 } 501 502 TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) { 503 ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr)); 504 ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr)); 505 } 506 507 TEST_F(InductionVarRangeTest, GetMulMin) { 508 ExpectEqual(Value(-14), GetMul(CreateConst(2), CreateRange(-7, 8), true)); 509 ExpectEqual(Value(-16), GetMul(CreateConst(-2), CreateRange(-7, 8), true)); 510 ExpectEqual(Value(-14), GetMul(CreateRange(-7, 8), CreateConst(2), true)); 511 ExpectEqual(Value(-16), GetMul(CreateRange(-7, 8), CreateConst(-2), true)); 512 ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true)); 513 ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true)); 514 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), true)); 515 ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true)); 516 ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true)); 517 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), true)); 518 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), true)); 519 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), true)); 520 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), true)); 521 } 522 523 TEST_F(InductionVarRangeTest, GetMulMax) { 524 ExpectEqual(Value(16), GetMul(CreateConst(2), CreateRange(-7, 8), false)); 525 ExpectEqual(Value(14), GetMul(CreateConst(-2), CreateRange(-7, 8), false)); 526 ExpectEqual(Value(16), GetMul(CreateRange(-7, 8), CreateConst(2), false)); 527 ExpectEqual(Value(14), GetMul(CreateRange(-7, 8), CreateConst(-2), false)); 528 ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false)); 529 ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false)); 530 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), false)); 531 ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false)); 532 ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false)); 533 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), false)); 534 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), false)); 535 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), false)); 536 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), false)); 537 } 538 539 TEST_F(InductionVarRangeTest, GetDivMin) { 540 ExpectEqual(Value(-5), GetDiv(CreateRange(-10, 20), CreateConst(2), true)); 541 ExpectEqual(Value(-10), GetDiv(CreateRange(-10, 20), CreateConst(-2), true)); 542 ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true)); 543 ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true)); 544 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), true)); 545 ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true)); 546 ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true)); 547 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), true)); 548 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), true)); 549 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, -40), true)); 550 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), true)); 551 } 552 553 TEST_F(InductionVarRangeTest, GetDivMax) { 554 ExpectEqual(Value(10), GetDiv(CreateRange(-10, 20), CreateConst(2), false)); 555 ExpectEqual(Value(5), GetDiv(CreateRange(-10, 20), CreateConst(-2), false)); 556 ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false)); 557 ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false)); 558 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), false)); 559 ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false)); 560 ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false)); 561 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), false)); 562 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), false)); 563 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, 40), false)); 564 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false)); 565 } 566 567 TEST_F(InductionVarRangeTest, GetMinMaxRem) { 568 ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr)); 569 ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateConst(2), CreateRange(10, 20)), nullptr)); 570 ExpectEqual(Value(), GetMin(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr)); 571 ExpectEqual(Value(), GetMax(CreateInvariant('%', CreateRange(10, 20), CreateConst(2)), nullptr)); 572 ExpectEqual(Value(2), GetMin(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr)); 573 ExpectEqual(Value(2), GetMax(CreateInvariant('%', CreateConst(2), CreateConst(5)), nullptr)); 574 ExpectEqual(Value(1), GetMin(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr)); 575 ExpectEqual(Value(1), GetMax(CreateInvariant('%', CreateConst(11), CreateConst(5)), nullptr)); 576 } 577 578 TEST_F(InductionVarRangeTest, GetRem) { 579 ExpectEqual(Value(0), GetRem(CreateConst(1), CreateConst(1))); 580 ExpectEqual(Value(2), GetRem(CreateConst(2), CreateConst(5))); 581 ExpectEqual(Value(1), GetRem(CreateConst(11), CreateConst(5))); 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(), GetRem(CreateConst(1), CreateConst(0))); 589 } 590 591 TEST_F(InductionVarRangeTest, GetMinMaxXor) { 592 ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr)); 593 ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateConst(2), CreateRange(10, 20)), nullptr)); 594 ExpectEqual(Value(), GetMin(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr)); 595 ExpectEqual(Value(), GetMax(CreateInvariant('^', CreateRange(10, 20), CreateConst(2)), nullptr)); 596 ExpectEqual(Value(3), GetMin(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr)); 597 ExpectEqual(Value(3), GetMax(CreateInvariant('^', CreateConst(1), CreateConst(2)), nullptr)); 598 } 599 600 TEST_F(InductionVarRangeTest, GetXor) { 601 ExpectEqual(Value(0), GetXor(CreateConst(1), CreateConst(1))); 602 ExpectEqual(Value(3), GetXor(CreateConst(1), CreateConst(2))); 603 ExpectEqual(Value(-2), GetXor(CreateConst(1), CreateConst(-1))); 604 ExpectEqual(Value(0), GetXor(CreateConst(-1), CreateConst(-1))); 605 } 606 607 TEST_F(InductionVarRangeTest, AddValue) { 608 ExpectEqual(Value(110), AddValue(Value(10), Value(100))); 609 ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1))); 610 ExpectEqual(Value(x_, 3, -5), AddValue(Value(x_, 2, -4), Value(x_, 1, -1))); 611 ExpectEqual(Value(), AddValue(Value(x_, 1, 5), Value(y_, 1, -7))); 612 ExpectEqual(Value(x_, 1, 23), AddValue(Value(x_, 1, 20), Value(3))); 613 ExpectEqual(Value(y_, 1, 5), AddValue(Value(55), Value(y_, 1, -50))); 614 const int32_t max_value = std::numeric_limits<int32_t>::max(); 615 ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5))); 616 ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe 617 } 618 619 TEST_F(InductionVarRangeTest, SubValue) { 620 ExpectEqual(Value(-90), SubValue(Value(10), Value(100))); 621 ExpectEqual(Value(-3), SubValue(Value(x_, 1, -4), Value(x_, 1, -1))); 622 ExpectEqual(Value(x_, 2, -3), SubValue(Value(x_, 3, -4), Value(x_, 1, -1))); 623 ExpectEqual(Value(), SubValue(Value(x_, 1, 5), Value(y_, 1, -7))); 624 ExpectEqual(Value(x_, 1, 17), SubValue(Value(x_, 1, 20), Value(3))); 625 ExpectEqual(Value(y_, -4, 105), SubValue(Value(55), Value(y_, 4, -50))); 626 const int32_t min_value = std::numeric_limits<int32_t>::min(); 627 ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5))); 628 ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe 629 } 630 631 TEST_F(InductionVarRangeTest, MulValue) { 632 ExpectEqual(Value(1000), MulValue(Value(10), Value(100))); 633 ExpectEqual(Value(), MulValue(Value(x_, 1, -4), Value(x_, 1, -1))); 634 ExpectEqual(Value(), MulValue(Value(x_, 1, 5), Value(y_, 1, -7))); 635 ExpectEqual(Value(x_, 9, 60), MulValue(Value(x_, 3, 20), Value(3))); 636 ExpectEqual(Value(y_, 55, -110), MulValue(Value(55), Value(y_, 1, -2))); 637 ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe 638 } 639 640 TEST_F(InductionVarRangeTest, MulValueSpecial) { 641 const int32_t min_value = std::numeric_limits<int32_t>::min(); 642 const int32_t max_value = std::numeric_limits<int32_t>::max(); 643 644 // Unsafe. 645 ExpectEqual(Value(), MulValue(Value(min_value), Value(min_value))); 646 ExpectEqual(Value(), MulValue(Value(min_value), Value(-1))); 647 ExpectEqual(Value(), MulValue(Value(min_value), Value(max_value))); 648 ExpectEqual(Value(), MulValue(Value(max_value), Value(max_value))); 649 650 // Safe. 651 ExpectEqual(Value(min_value), MulValue(Value(min_value), Value(1))); 652 ExpectEqual(Value(max_value), MulValue(Value(max_value), Value(1))); 653 ExpectEqual(Value(-max_value), MulValue(Value(max_value), Value(-1))); 654 ExpectEqual(Value(-1), MulValue(Value(1), Value(-1))); 655 ExpectEqual(Value(1), MulValue(Value(-1), Value(-1))); 656 } 657 658 TEST_F(InductionVarRangeTest, DivValue) { 659 ExpectEqual(Value(25), DivValue(Value(100), Value(4))); 660 ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1))); 661 ExpectEqual(Value(), DivValue(Value(x_, 1, 5), Value(y_, 1, -7))); 662 ExpectEqual(Value(), DivValue(Value(x_, 12, 24), Value(3))); 663 ExpectEqual(Value(), DivValue(Value(55), Value(y_, 1, -50))); 664 ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe 665 } 666 667 TEST_F(InductionVarRangeTest, DivValueSpecial) { 668 const int32_t min_value = std::numeric_limits<int32_t>::min(); 669 const int32_t max_value = std::numeric_limits<int32_t>::max(); 670 671 // Unsafe. 672 ExpectEqual(Value(), DivValue(Value(min_value), Value(-1))); 673 674 // Safe. 675 ExpectEqual(Value(1), DivValue(Value(min_value), Value(min_value))); 676 ExpectEqual(Value(1), DivValue(Value(max_value), Value(max_value))); 677 ExpectEqual(Value(min_value), DivValue(Value(min_value), Value(1))); 678 ExpectEqual(Value(max_value), DivValue(Value(max_value), Value(1))); 679 ExpectEqual(Value(-max_value), DivValue(Value(max_value), Value(-1))); 680 ExpectEqual(Value(-1), DivValue(Value(1), Value(-1))); 681 ExpectEqual(Value(1), DivValue(Value(-1), Value(-1))); 682 } 683 684 TEST_F(InductionVarRangeTest, MinValue) { 685 ExpectEqual(Value(10), MinValue(Value(10), Value(100))); 686 ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1))); 687 ExpectEqual(Value(x_, 4, -4), MinValue(Value(x_, 4, -4), Value(x_, 4, -1))); 688 ExpectEqual(Value(), MinValue(Value(x_, 1, 5), Value(y_, 1, -7))); 689 ExpectEqual(Value(), MinValue(Value(x_, 1, 20), Value(3))); 690 ExpectEqual(Value(), MinValue(Value(55), Value(y_, 1, -50))); 691 } 692 693 TEST_F(InductionVarRangeTest, MaxValue) { 694 ExpectEqual(Value(100), MaxValue(Value(10), Value(100))); 695 ExpectEqual(Value(x_, 1, -1), MaxValue(Value(x_, 1, -4), Value(x_, 1, -1))); 696 ExpectEqual(Value(x_, 4, -1), MaxValue(Value(x_, 4, -4), Value(x_, 4, -1))); 697 ExpectEqual(Value(), MaxValue(Value(x_, 1, 5), Value(y_, 1, -7))); 698 ExpectEqual(Value(), MaxValue(Value(x_, 1, 20), Value(3))); 699 ExpectEqual(Value(), MaxValue(Value(55), Value(y_, 1, -50))); 700 } 701 702 TEST_F(InductionVarRangeTest, ArrayLengthAndHints) { 703 // We pass a bogus constant for the class to avoid mocking one. 704 HInstruction* new_array = new (GetAllocator()) HNewArray(x_, x_, 0); 705 entry_block_->AddInstruction(new_array); 706 HInstruction* array_length = new (GetAllocator()) HArrayLength(new_array, 0); 707 entry_block_->AddInstruction(array_length); 708 // With null hint: yields extreme constants. 709 const int32_t max_value = std::numeric_limits<int32_t>::max(); 710 SetHint(nullptr); 711 ExpectEqual(Value(0), GetMin(CreateFetch(array_length), nullptr)); 712 ExpectEqual(Value(max_value), GetMax(CreateFetch(array_length), nullptr)); 713 // With explicit hint: yields the length instruction. 714 SetHint(array_length); 715 ExpectEqual(Value(array_length, 1, 0), GetMin(CreateFetch(array_length), nullptr)); 716 ExpectEqual(Value(array_length, 1, 0), GetMax(CreateFetch(array_length), nullptr)); 717 // With any non-null hint: chases beyond the length instruction. 718 SetHint(x_); 719 ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(array_length), nullptr)); 720 ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(array_length), nullptr)); 721 } 722 723 TEST_F(InductionVarRangeTest, AddOrSubAndConstant) { 724 HInstruction* add = new (GetAllocator()) 725 HAdd(DataType::Type::kInt32, x_, graph_->GetIntConstant(-1)); 726 HInstruction* alt = new (GetAllocator()) 727 HAdd(DataType::Type::kInt32, graph_->GetIntConstant(-1), x_); 728 HInstruction* sub = new (GetAllocator()) 729 HSub(DataType::Type::kInt32, x_, graph_->GetIntConstant(1)); 730 HInstruction* rev = new (GetAllocator()) 731 HSub(DataType::Type::kInt32, graph_->GetIntConstant(1), x_); 732 entry_block_->AddInstruction(add); 733 entry_block_->AddInstruction(alt); 734 entry_block_->AddInstruction(sub); 735 entry_block_->AddInstruction(rev); 736 ExpectEqual(Value(x_, 1, -1), GetMin(CreateFetch(add), nullptr)); 737 ExpectEqual(Value(x_, 1, -1), GetMax(CreateFetch(add), nullptr)); 738 ExpectEqual(Value(x_, 1, -1), GetMin(CreateFetch(alt), nullptr)); 739 ExpectEqual(Value(x_, 1, -1), GetMax(CreateFetch(alt), nullptr)); 740 ExpectEqual(Value(x_, 1, -1), GetMin(CreateFetch(sub), nullptr)); 741 ExpectEqual(Value(x_, 1, -1), GetMax(CreateFetch(sub), nullptr)); 742 ExpectEqual(Value(x_, -1, 1), GetMin(CreateFetch(rev), nullptr)); 743 ExpectEqual(Value(x_, -1, 1), GetMax(CreateFetch(rev), nullptr)); 744 } 745 746 // 747 // Tests on public methods. 748 // 749 750 TEST_F(InductionVarRangeTest, ConstantTripCountUp) { 751 BuildLoop(0, graph_->GetIntConstant(1000), 1); 752 PerformInductionVarAnalysis(); 753 754 Value v1, v2; 755 bool needs_finite_test = true; 756 bool needs_taken_test = true; 757 758 HInstruction* phi = condition_->InputAt(0); 759 HInstruction* exit = exit_block_->GetLastInstruction(); 760 761 // In context of header: known. 762 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); 763 EXPECT_FALSE(needs_finite_test); 764 ExpectEqual(Value(0), v1); 765 ExpectEqual(Value(1000), v2); 766 767 // In context of loop-body: known. 768 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); 769 EXPECT_FALSE(needs_finite_test); 770 ExpectEqual(Value(0), v1); 771 ExpectEqual(Value(999), v2); 772 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 773 EXPECT_FALSE(needs_finite_test); 774 ExpectEqual(Value(1), v1); 775 ExpectEqual(Value(1000), v2); 776 777 // Induction vs. no-induction. 778 EXPECT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); 779 EXPECT_TRUE(range_.CanGenerateLastValue(phi)); 780 EXPECT_FALSE(range_.CanGenerateRange(exit, exit, &needs_finite_test, &needs_taken_test)); 781 EXPECT_FALSE(range_.CanGenerateLastValue(exit)); 782 783 // Last value (unsimplified). 784 HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_); 785 ASSERT_TRUE(last->IsAdd()); 786 ExpectInt(1000, last->InputAt(0)); 787 ExpectInt(0, last->InputAt(1)); 788 789 // Loop logic. 790 int64_t tc = 0; 791 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc)); 792 EXPECT_EQ(1000, tc); 793 HInstruction* offset = nullptr; 794 EXPECT_TRUE(range_.IsUnitStride(phi, phi, graph_, &offset)); 795 ExpectInt(0, offset); 796 HInstruction* tce = range_.GenerateTripCount( 797 loop_header_->GetLoopInformation(), graph_, loop_preheader_); 798 ASSERT_TRUE(tce != nullptr); 799 ExpectInt(1000, tce); 800 } 801 802 TEST_F(InductionVarRangeTest, ConstantTripCountDown) { 803 BuildLoop(1000, graph_->GetIntConstant(0), -1); 804 PerformInductionVarAnalysis(); 805 806 Value v1, v2; 807 bool needs_finite_test = true; 808 bool needs_taken_test = true; 809 810 HInstruction* phi = condition_->InputAt(0); 811 HInstruction* exit = exit_block_->GetLastInstruction(); 812 813 // In context of header: known. 814 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); 815 EXPECT_FALSE(needs_finite_test); 816 ExpectEqual(Value(0), v1); 817 ExpectEqual(Value(1000), v2); 818 819 // In context of loop-body: known. 820 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); 821 EXPECT_FALSE(needs_finite_test); 822 ExpectEqual(Value(1), v1); 823 ExpectEqual(Value(1000), v2); 824 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 825 EXPECT_FALSE(needs_finite_test); 826 ExpectEqual(Value(0), v1); 827 ExpectEqual(Value(999), v2); 828 829 // Induction vs. no-induction. 830 EXPECT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); 831 EXPECT_TRUE(range_.CanGenerateLastValue(phi)); 832 EXPECT_FALSE(range_.CanGenerateRange(exit, exit, &needs_finite_test, &needs_taken_test)); 833 EXPECT_FALSE(range_.CanGenerateLastValue(exit)); 834 835 // Last value (unsimplified). 836 HInstruction* last = range_.GenerateLastValue(phi, graph_, loop_preheader_); 837 ASSERT_TRUE(last->IsSub()); 838 ExpectInt(1000, last->InputAt(0)); 839 ASSERT_TRUE(last->InputAt(1)->IsNeg()); 840 last = last->InputAt(1)->InputAt(0); 841 ASSERT_TRUE(last->IsSub()); 842 ExpectInt(0, last->InputAt(0)); 843 ExpectInt(1000, last->InputAt(1)); 844 845 // Loop logic. 846 int64_t tc = 0; 847 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc)); 848 EXPECT_EQ(1000, tc); 849 HInstruction* offset = nullptr; 850 EXPECT_FALSE(range_.IsUnitStride(phi, phi, graph_, &offset)); 851 HInstruction* tce = range_.GenerateTripCount( 852 loop_header_->GetLoopInformation(), graph_, loop_preheader_); 853 ASSERT_TRUE(tce != nullptr); 854 ASSERT_TRUE(tce->IsNeg()); 855 last = tce->InputAt(0); 856 EXPECT_TRUE(last->IsSub()); 857 ExpectInt(0, last->InputAt(0)); 858 ExpectInt(1000, last->InputAt(1)); 859 } 860 861 TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { 862 BuildLoop(0, x_, 1); 863 PerformInductionVarAnalysis(); 864 865 Value v1, v2; 866 bool needs_finite_test = true; 867 bool needs_taken_test = true; 868 869 HInstruction* phi = condition_->InputAt(0); 870 871 // In context of header: upper unknown. 872 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); 873 EXPECT_FALSE(needs_finite_test); 874 ExpectEqual(Value(0), v1); 875 ExpectEqual(Value(), v2); 876 877 // In context of loop-body: known. 878 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); 879 EXPECT_FALSE(needs_finite_test); 880 ExpectEqual(Value(0), v1); 881 ExpectEqual(Value(x_, 1, -1), v2); 882 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 883 EXPECT_FALSE(needs_finite_test); 884 ExpectEqual(Value(1), v1); 885 ExpectEqual(Value(x_, 1, 0), v2); 886 887 HInstruction* lower = nullptr; 888 HInstruction* upper = nullptr; 889 890 // Can generate code in context of loop-body only. 891 EXPECT_FALSE(range_.CanGenerateRange(condition_, phi, &needs_finite_test, &needs_taken_test)); 892 ASSERT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); 893 EXPECT_FALSE(needs_finite_test); 894 EXPECT_TRUE(needs_taken_test); 895 896 // Generates code (unsimplified). 897 range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper); 898 899 // Verify lower is 0+0. 900 ASSERT_TRUE(lower != nullptr); 901 ASSERT_TRUE(lower->IsAdd()); 902 ExpectInt(0, lower->InputAt(0)); 903 ExpectInt(0, lower->InputAt(1)); 904 905 // Verify upper is (V-1)+0. 906 ASSERT_TRUE(upper != nullptr); 907 ASSERT_TRUE(upper->IsAdd()); 908 ASSERT_TRUE(upper->InputAt(0)->IsSub()); 909 EXPECT_TRUE(upper->InputAt(0)->InputAt(0)->IsParameterValue()); 910 ExpectInt(1, upper->InputAt(0)->InputAt(1)); 911 ExpectInt(0, upper->InputAt(1)); 912 913 // Verify taken-test is 0<V. 914 HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_); 915 ASSERT_TRUE(taken != nullptr); 916 ASSERT_TRUE(taken->IsLessThan()); 917 ExpectInt(0, taken->InputAt(0)); 918 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); 919 920 // Replacement. 921 range_.Replace(loop_header_->GetLastInstruction(), x_, y_); 922 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 923 EXPECT_FALSE(needs_finite_test); 924 ExpectEqual(Value(1), v1); 925 ExpectEqual(Value(y_, 1, 0), v2); 926 927 // Loop logic. 928 int64_t tc = 0; 929 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc)); 930 EXPECT_EQ(0, tc); // unknown 931 HInstruction* offset = nullptr; 932 EXPECT_TRUE(range_.IsUnitStride(phi, phi, graph_, &offset)); 933 ExpectInt(0, offset); 934 HInstruction* tce = range_.GenerateTripCount( 935 loop_header_->GetLoopInformation(), graph_, loop_preheader_); 936 ASSERT_TRUE(tce != nullptr); 937 EXPECT_TRUE(tce->IsSelect()); // guarded by taken-test 938 ExpectInt(0, tce->InputAt(0)); 939 EXPECT_TRUE(tce->InputAt(1)->IsParameterValue()); 940 EXPECT_TRUE(tce->InputAt(2)->IsLessThan()); 941 } 942 943 TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { 944 BuildLoop(1000, x_, -1); 945 PerformInductionVarAnalysis(); 946 947 Value v1, v2; 948 bool needs_finite_test = true; 949 bool needs_taken_test = true; 950 951 HInstruction* phi = condition_->InputAt(0); 952 953 // In context of header: lower unknown. 954 range_.GetInductionRange(condition_, phi, x_, &v1, &v2, &needs_finite_test); 955 EXPECT_FALSE(needs_finite_test); 956 ExpectEqual(Value(), v1); 957 ExpectEqual(Value(1000), v2); 958 959 // In context of loop-body: known. 960 range_.GetInductionRange(increment_, phi, x_, &v1, &v2, &needs_finite_test); 961 EXPECT_FALSE(needs_finite_test); 962 ExpectEqual(Value(x_, 1, 1), v1); 963 ExpectEqual(Value(1000), v2); 964 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 965 EXPECT_FALSE(needs_finite_test); 966 ExpectEqual(Value(x_, 1, 0), v1); 967 ExpectEqual(Value(999), v2); 968 969 HInstruction* lower = nullptr; 970 HInstruction* upper = nullptr; 971 972 // Can generate code in context of loop-body only. 973 EXPECT_FALSE(range_.CanGenerateRange(condition_, phi, &needs_finite_test, &needs_taken_test)); 974 ASSERT_TRUE(range_.CanGenerateRange(increment_, phi, &needs_finite_test, &needs_taken_test)); 975 EXPECT_FALSE(needs_finite_test); 976 EXPECT_TRUE(needs_taken_test); 977 978 // Generates code (unsimplified). 979 range_.GenerateRange(increment_, phi, graph_, loop_preheader_, &lower, &upper); 980 981 // Verify lower is 1000-((1000-V)-1). 982 ASSERT_TRUE(lower != nullptr); 983 ASSERT_TRUE(lower->IsSub()); 984 ExpectInt(1000, lower->InputAt(0)); 985 lower = lower->InputAt(1); 986 ASSERT_TRUE(lower->IsSub()); 987 ExpectInt(1, lower->InputAt(1)); 988 lower = lower->InputAt(0); 989 ASSERT_TRUE(lower->IsSub()); 990 ExpectInt(1000, lower->InputAt(0)); 991 EXPECT_TRUE(lower->InputAt(1)->IsParameterValue()); 992 993 // Verify upper is 1000-0. 994 ASSERT_TRUE(upper != nullptr); 995 ASSERT_TRUE(upper->IsSub()); 996 ExpectInt(1000, upper->InputAt(0)); 997 ExpectInt(0, upper->InputAt(1)); 998 999 // Verify taken-test is 1000>V. 1000 HInstruction* taken = range_.GenerateTakenTest(increment_, graph_, loop_preheader_); 1001 ASSERT_TRUE(taken != nullptr); 1002 ASSERT_TRUE(taken->IsGreaterThan()); 1003 ExpectInt(1000, taken->InputAt(0)); 1004 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); 1005 1006 // Replacement. 1007 range_.Replace(loop_header_->GetLastInstruction(), x_, y_); 1008 range_.GetInductionRange(increment_, increment_, x_, &v1, &v2, &needs_finite_test); 1009 EXPECT_FALSE(needs_finite_test); 1010 ExpectEqual(Value(y_, 1, 0), v1); 1011 ExpectEqual(Value(999), v2); 1012 1013 // Loop logic. 1014 int64_t tc = 0; 1015 EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc)); 1016 EXPECT_EQ(0, tc); // unknown 1017 HInstruction* offset = nullptr; 1018 EXPECT_FALSE(range_.IsUnitStride(phi, phi, graph_, &offset)); 1019 HInstruction* tce = range_.GenerateTripCount( 1020 loop_header_->GetLoopInformation(), graph_, loop_preheader_); 1021 ASSERT_TRUE(tce != nullptr); 1022 EXPECT_TRUE(tce->IsSelect()); // guarded by taken-test 1023 ExpectInt(0, tce->InputAt(0)); 1024 EXPECT_TRUE(tce->InputAt(1)->IsSub()); 1025 EXPECT_TRUE(tce->InputAt(2)->IsGreaterThan()); 1026 tce = tce->InputAt(1); 1027 ExpectInt(1000, taken->InputAt(0)); 1028 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); 1029 } 1030 1031 } // namespace art 1032
