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 // 52 // Construction methods. 53 // 54 55 /** Constructs bare minimum graph. */ 56 void BuildGraph() { 57 graph_->SetNumberOfVRegs(1); 58 entry_block_ = new (&allocator_) HBasicBlock(graph_); 59 exit_block_ = new (&allocator_) HBasicBlock(graph_); 60 graph_->AddBlock(entry_block_); 61 graph_->AddBlock(exit_block_); 62 graph_->SetEntryBlock(entry_block_); 63 graph_->SetExitBlock(exit_block_); 64 // Two parameters. 65 x_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); 66 entry_block_->AddInstruction(x_); 67 y_ = new (&allocator_) HParameterValue(graph_->GetDexFile(), 0, 0, Primitive::kPrimInt); 68 entry_block_->AddInstruction(y_); 69 } 70 71 /** Constructs loop with given upper bound. */ 72 void BuildLoop(int32_t lower, HInstruction* upper, int32_t stride) { 73 // Control flow. 74 loop_preheader_ = new (&allocator_) HBasicBlock(graph_); 75 graph_->AddBlock(loop_preheader_); 76 HBasicBlock* loop_header = new (&allocator_) HBasicBlock(graph_); 77 graph_->AddBlock(loop_header); 78 HBasicBlock* loop_body = new (&allocator_) HBasicBlock(graph_); 79 graph_->AddBlock(loop_body); 80 HBasicBlock* return_block = new (&allocator_) HBasicBlock(graph_); 81 graph_->AddBlock(return_block); 82 entry_block_->AddSuccessor(loop_preheader_); 83 loop_preheader_->AddSuccessor(loop_header); 84 loop_header->AddSuccessor(loop_body); 85 loop_header->AddSuccessor(return_block); 86 loop_body->AddSuccessor(loop_header); 87 return_block->AddSuccessor(exit_block_); 88 // Instructions. 89 loop_preheader_->AddInstruction(new (&allocator_) HGoto()); 90 HPhi* phi = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt); 91 loop_header->AddPhi(phi); 92 phi->AddInput(graph_->GetIntConstant(lower)); // i = l 93 if (stride > 0) { 94 condition_ = new (&allocator_) HLessThan(phi, upper); // i < u 95 } else { 96 condition_ = new (&allocator_) HGreaterThan(phi, upper); // i > u 97 } 98 loop_header->AddInstruction(condition_); 99 loop_header->AddInstruction(new (&allocator_) HIf(condition_)); 100 increment_ = new (&allocator_) HAdd(Primitive::kPrimInt, phi, graph_->GetIntConstant(stride)); 101 loop_body->AddInstruction(increment_); // i += s 102 phi->AddInput(increment_); 103 loop_body->AddInstruction(new (&allocator_) HGoto()); 104 return_block->AddInstruction(new (&allocator_) HReturnVoid()); 105 exit_block_->AddInstruction(new (&allocator_) HExit()); 106 } 107 108 /** Constructs SSA and performs induction variable analysis. */ 109 void PerformInductionVarAnalysis() { 110 graph_->BuildDominatorTree(); 111 iva_->Run(); 112 } 113 114 /** Constructs an invariant. */ 115 HInductionVarAnalysis::InductionInfo* CreateInvariant(char opc, 116 HInductionVarAnalysis::InductionInfo* a, 117 HInductionVarAnalysis::InductionInfo* b) { 118 HInductionVarAnalysis::InductionOp op; 119 switch (opc) { 120 case '+': op = HInductionVarAnalysis::kAdd; break; 121 case '-': op = HInductionVarAnalysis::kSub; break; 122 case 'n': op = HInductionVarAnalysis::kNeg; break; 123 case '*': op = HInductionVarAnalysis::kMul; break; 124 case '/': op = HInductionVarAnalysis::kDiv; break; 125 default: op = HInductionVarAnalysis::kNop; break; 126 } 127 return iva_->CreateInvariantOp(op, a, b); 128 } 129 130 /** Constructs a fetch. */ 131 HInductionVarAnalysis::InductionInfo* CreateFetch(HInstruction* fetch) { 132 return iva_->CreateInvariantFetch(fetch); 133 } 134 135 /** Constructs a constant. */ 136 HInductionVarAnalysis::InductionInfo* CreateConst(int32_t c) { 137 return CreateFetch(graph_->GetIntConstant(c)); 138 } 139 140 /** Constructs a trip-count. */ 141 HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc, bool in_loop, bool safe) { 142 Primitive::Type type = Primitive::kPrimInt; 143 if (in_loop && safe) { 144 return iva_->CreateTripCount( 145 HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc), nullptr, type); 146 } else if (in_loop) { 147 return iva_->CreateTripCount( 148 HInductionVarAnalysis::kTripCountInLoopUnsafe, CreateConst(tc), nullptr, type); 149 } else if (safe) { 150 return iva_->CreateTripCount( 151 HInductionVarAnalysis::kTripCountInBody, CreateConst(tc), nullptr, type); 152 } else { 153 return iva_->CreateTripCount( 154 HInductionVarAnalysis::kTripCountInBodyUnsafe, CreateConst(tc), nullptr, type); 155 } 156 } 157 158 /** Constructs a linear a * i + b induction. */ 159 HInductionVarAnalysis::InductionInfo* CreateLinear(int32_t a, int32_t b) { 160 return iva_->CreateInduction( 161 HInductionVarAnalysis::kLinear, CreateConst(a), CreateConst(b), Primitive::kPrimInt); 162 } 163 164 /** Constructs a range [lo, hi] using a periodic induction. */ 165 HInductionVarAnalysis::InductionInfo* CreateRange(int32_t lo, int32_t hi) { 166 return iva_->CreateInduction( 167 HInductionVarAnalysis::kPeriodic, CreateConst(lo), CreateConst(hi), Primitive::kPrimInt); 168 } 169 170 /** Constructs a wrap-around induction consisting of a constant, followed info */ 171 HInductionVarAnalysis::InductionInfo* CreateWrapAround( 172 int32_t initial, 173 HInductionVarAnalysis::InductionInfo* info) { 174 return iva_->CreateInduction( 175 HInductionVarAnalysis::kWrapAround, CreateConst(initial), info, Primitive::kPrimInt); 176 } 177 178 /** Constructs a wrap-around induction consisting of a constant, followed by a range. */ 179 HInductionVarAnalysis::InductionInfo* CreateWrapAround(int32_t initial, int32_t lo, int32_t hi) { 180 return CreateWrapAround(initial, CreateRange(lo, hi)); 181 } 182 183 // 184 // Relay methods. 185 // 186 187 bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) { 188 return range_.NeedsTripCount(info); 189 } 190 191 bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) { 192 return range_.IsBodyTripCount(trip); 193 } 194 195 bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) { 196 return range_.IsUnsafeTripCount(trip); 197 } 198 199 Value GetMin(HInductionVarAnalysis::InductionInfo* info, 200 HInductionVarAnalysis::InductionInfo* induc) { 201 return range_.GetVal(info, induc, /* in_body */ true, /* is_min */ true); 202 } 203 204 Value GetMax(HInductionVarAnalysis::InductionInfo* info, 205 HInductionVarAnalysis::InductionInfo* induc) { 206 return range_.GetVal(info, induc, /* in_body */ true, /* is_min */ false); 207 } 208 209 Value GetMul(HInductionVarAnalysis::InductionInfo* info1, 210 HInductionVarAnalysis::InductionInfo* info2, 211 bool is_min) { 212 return range_.GetMul(info1, info2, nullptr, /* in_body */ true, is_min); 213 } 214 215 Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, 216 HInductionVarAnalysis::InductionInfo* info2, 217 bool is_min) { 218 return range_.GetDiv(info1, info2, nullptr, /* in_body */ true, is_min); 219 } 220 221 bool IsExact(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { 222 return range_.IsConstant(info, InductionVarRange::kExact, value); 223 } 224 225 bool IsAtMost(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { 226 return range_.IsConstant(info, InductionVarRange::kAtMost, value); 227 } 228 229 bool IsAtLeast(HInductionVarAnalysis::InductionInfo* info, int64_t* value) { 230 return range_.IsConstant(info, InductionVarRange::kAtLeast, value); 231 } 232 233 Value AddValue(Value v1, Value v2) { return range_.AddValue(v1, v2); } 234 Value SubValue(Value v1, Value v2) { return range_.SubValue(v1, v2); } 235 Value MulValue(Value v1, Value v2) { return range_.MulValue(v1, v2); } 236 Value DivValue(Value v1, Value v2) { return range_.DivValue(v1, v2); } 237 Value MinValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, true); } 238 Value MaxValue(Value v1, Value v2) { return range_.MergeVal(v1, v2, false); } 239 240 // General building fields. 241 ArenaPool pool_; 242 ArenaAllocator allocator_; 243 HGraph* graph_; 244 HBasicBlock* entry_block_; 245 HBasicBlock* exit_block_; 246 HBasicBlock* loop_preheader_; 247 HInductionVarAnalysis* iva_; 248 InductionVarRange range_; 249 250 // Instructions. 251 HInstruction* condition_; 252 HInstruction* increment_; 253 HInstruction* x_; 254 HInstruction* y_; 255 }; 256 257 // 258 // Tests on private methods. 259 // 260 261 TEST_F(InductionVarRangeTest, IsConstant) { 262 int64_t value; 263 // Constant. 264 EXPECT_TRUE(IsExact(CreateConst(12345), &value)); 265 EXPECT_EQ(12345, value); 266 EXPECT_TRUE(IsAtMost(CreateConst(12345), &value)); 267 EXPECT_EQ(12345, value); 268 EXPECT_TRUE(IsAtLeast(CreateConst(12345), &value)); 269 EXPECT_EQ(12345, value); 270 // Constant trivial range. 271 EXPECT_TRUE(IsExact(CreateRange(111, 111), &value)); 272 EXPECT_EQ(111, value); 273 EXPECT_TRUE(IsAtMost(CreateRange(111, 111), &value)); 274 EXPECT_EQ(111, value); 275 EXPECT_TRUE(IsAtLeast(CreateRange(111, 111), &value)); 276 EXPECT_EQ(111, value); 277 // Constant non-trivial range. 278 EXPECT_FALSE(IsExact(CreateRange(11, 22), &value)); 279 EXPECT_TRUE(IsAtMost(CreateRange(11, 22), &value)); 280 EXPECT_EQ(22, value); 281 EXPECT_TRUE(IsAtLeast(CreateRange(11, 22), &value)); 282 EXPECT_EQ(11, value); 283 // Symbolic. 284 EXPECT_FALSE(IsExact(CreateFetch(x_), &value)); 285 EXPECT_FALSE(IsAtMost(CreateFetch(x_), &value)); 286 EXPECT_FALSE(IsAtLeast(CreateFetch(x_), &value)); 287 } 288 289 TEST_F(InductionVarRangeTest, TripCountProperties) { 290 EXPECT_FALSE(NeedsTripCount(nullptr)); 291 EXPECT_FALSE(NeedsTripCount(CreateConst(1))); 292 EXPECT_TRUE(NeedsTripCount(CreateLinear(1, 1))); 293 EXPECT_FALSE(NeedsTripCount(CreateWrapAround(1, 2, 3))); 294 EXPECT_TRUE(NeedsTripCount(CreateWrapAround(1, CreateLinear(1, 1)))); 295 296 EXPECT_FALSE(IsBodyTripCount(nullptr)); 297 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, true))); 298 EXPECT_FALSE(IsBodyTripCount(CreateTripCount(100, true, false))); 299 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, true))); 300 EXPECT_TRUE(IsBodyTripCount(CreateTripCount(100, false, false))); 301 302 EXPECT_FALSE(IsUnsafeTripCount(nullptr)); 303 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, true, true))); 304 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, true, false))); 305 EXPECT_FALSE(IsUnsafeTripCount(CreateTripCount(100, false, true))); 306 EXPECT_TRUE(IsUnsafeTripCount(CreateTripCount(100, false, false))); 307 } 308 309 TEST_F(InductionVarRangeTest, GetMinMaxNull) { 310 ExpectEqual(Value(), GetMin(nullptr, nullptr)); 311 ExpectEqual(Value(), GetMax(nullptr, nullptr)); 312 } 313 314 TEST_F(InductionVarRangeTest, GetMinMaxAdd) { 315 ExpectEqual(Value(12), 316 GetMin(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); 317 ExpectEqual(Value(22), 318 GetMax(CreateInvariant('+', CreateConst(2), CreateRange(10, 20)), nullptr)); 319 ExpectEqual(Value(x_, 1, -20), 320 GetMin(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 321 ExpectEqual(Value(x_, 1, -10), 322 GetMax(CreateInvariant('+', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 323 ExpectEqual(Value(x_, 1, 10), 324 GetMin(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 325 ExpectEqual(Value(x_, 1, 20), 326 GetMax(CreateInvariant('+', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 327 ExpectEqual(Value(5), 328 GetMin(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 329 ExpectEqual(Value(19), 330 GetMax(CreateInvariant('+', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 331 } 332 333 TEST_F(InductionVarRangeTest, GetMinMaxSub) { 334 ExpectEqual(Value(-18), 335 GetMin(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); 336 ExpectEqual(Value(-8), 337 GetMax(CreateInvariant('-', CreateConst(2), CreateRange(10, 20)), nullptr)); 338 ExpectEqual(Value(x_, 1, 10), 339 GetMin(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 340 ExpectEqual(Value(x_, 1, 20), 341 GetMax(CreateInvariant('-', CreateFetch(x_), CreateRange(-20, -10)), nullptr)); 342 ExpectEqual(Value(x_, -1, 10), 343 GetMin(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 344 ExpectEqual(Value(x_, -1, 20), 345 GetMax(CreateInvariant('-', CreateRange(10, 20), CreateFetch(x_)), nullptr)); 346 ExpectEqual(Value(-25), 347 GetMin(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 348 ExpectEqual(Value(-11), 349 GetMax(CreateInvariant('-', CreateRange(-5, -1), CreateRange(10, 20)), nullptr)); 350 } 351 352 TEST_F(InductionVarRangeTest, GetMinMaxNeg) { 353 ExpectEqual(Value(-20), GetMin(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); 354 ExpectEqual(Value(-10), GetMax(CreateInvariant('n', nullptr, CreateRange(10, 20)), nullptr)); 355 ExpectEqual(Value(10), GetMin(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); 356 ExpectEqual(Value(20), GetMax(CreateInvariant('n', nullptr, CreateRange(-20, -10)), nullptr)); 357 ExpectEqual(Value(x_, -1, 0), GetMin(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr)); 358 ExpectEqual(Value(x_, -1, 0), GetMax(CreateInvariant('n', nullptr, CreateFetch(x_)), nullptr)); 359 } 360 361 TEST_F(InductionVarRangeTest, GetMinMaxMul) { 362 ExpectEqual(Value(20), 363 GetMin(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); 364 ExpectEqual(Value(40), 365 GetMax(CreateInvariant('*', CreateConst(2), CreateRange(10, 20)), nullptr)); 366 } 367 368 TEST_F(InductionVarRangeTest, GetMinMaxDiv) { 369 ExpectEqual(Value(3), 370 GetMin(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); 371 ExpectEqual(Value(5), 372 GetMax(CreateInvariant('/', CreateRange(12, 20), CreateConst(4)), nullptr)); 373 } 374 375 TEST_F(InductionVarRangeTest, GetMinMaxConstant) { 376 ExpectEqual(Value(12345), GetMin(CreateConst(12345), nullptr)); 377 ExpectEqual(Value(12345), GetMax(CreateConst(12345), nullptr)); 378 } 379 380 TEST_F(InductionVarRangeTest, GetMinMaxFetch) { 381 ExpectEqual(Value(x_, 1, 0), GetMin(CreateFetch(x_), nullptr)); 382 ExpectEqual(Value(x_, 1, 0), GetMax(CreateFetch(x_), nullptr)); 383 } 384 385 TEST_F(InductionVarRangeTest, GetMinMaxLinear) { 386 ExpectEqual(Value(20), GetMin(CreateLinear(10, 20), CreateTripCount(100, true, true))); 387 ExpectEqual(Value(1010), GetMax(CreateLinear(10, 20), CreateTripCount(100, true, true))); 388 ExpectEqual(Value(-970), GetMin(CreateLinear(-10, 20), CreateTripCount(100, true, true))); 389 ExpectEqual(Value(20), GetMax(CreateLinear(-10, 20), CreateTripCount(100, true, true))); 390 } 391 392 TEST_F(InductionVarRangeTest, GetMinMaxWrapAround) { 393 ExpectEqual(Value(-5), GetMin(CreateWrapAround(-5, -1, 10), nullptr)); 394 ExpectEqual(Value(10), GetMax(CreateWrapAround(-5, -1, 10), nullptr)); 395 ExpectEqual(Value(-1), GetMin(CreateWrapAround(2, -1, 10), nullptr)); 396 ExpectEqual(Value(10), GetMax(CreateWrapAround(2, -1, 10), nullptr)); 397 ExpectEqual(Value(-1), GetMin(CreateWrapAround(20, -1, 10), nullptr)); 398 ExpectEqual(Value(20), GetMax(CreateWrapAround(20, -1, 10), nullptr)); 399 } 400 401 TEST_F(InductionVarRangeTest, GetMinMaxPeriodic) { 402 ExpectEqual(Value(-2), GetMin(CreateRange(-2, 99), nullptr)); 403 ExpectEqual(Value(99), GetMax(CreateRange(-2, 99), nullptr)); 404 } 405 406 TEST_F(InductionVarRangeTest, GetMulMin) { 407 ExpectEqual(Value(-14), GetMul(CreateConst(2), CreateRange(-7, 8), true)); 408 ExpectEqual(Value(-16), GetMul(CreateConst(-2), CreateRange(-7, 8), true)); 409 ExpectEqual(Value(-14), GetMul(CreateRange(-7, 8), CreateConst(2), true)); 410 ExpectEqual(Value(-16), GetMul(CreateRange(-7, 8), CreateConst(-2), true)); 411 ExpectEqual(Value(6), GetMul(CreateRange(2, 10), CreateRange(3, 5), true)); 412 ExpectEqual(Value(-50), GetMul(CreateRange(2, 10), CreateRange(-5, -3), true)); 413 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), true)); 414 ExpectEqual(Value(-50), GetMul(CreateRange(-10, -2), CreateRange(3, 5), true)); 415 ExpectEqual(Value(6), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), true)); 416 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), true)); 417 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), true)); 418 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), true)); 419 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), true)); 420 } 421 422 TEST_F(InductionVarRangeTest, GetMulMax) { 423 ExpectEqual(Value(16), GetMul(CreateConst(2), CreateRange(-7, 8), false)); 424 ExpectEqual(Value(14), GetMul(CreateConst(-2), CreateRange(-7, 8), false)); 425 ExpectEqual(Value(16), GetMul(CreateRange(-7, 8), CreateConst(2), false)); 426 ExpectEqual(Value(14), GetMul(CreateRange(-7, 8), CreateConst(-2), false)); 427 ExpectEqual(Value(50), GetMul(CreateRange(2, 10), CreateRange(3, 5), false)); 428 ExpectEqual(Value(-6), GetMul(CreateRange(2, 10), CreateRange(-5, -3), false)); 429 ExpectEqual(Value(), GetMul(CreateRange(2, 10), CreateRange(-1, 1), false)); 430 ExpectEqual(Value(-6), GetMul(CreateRange(-10, -2), CreateRange(3, 5), false)); 431 ExpectEqual(Value(50), GetMul(CreateRange(-10, -2), CreateRange(-5, -3), false)); 432 ExpectEqual(Value(), GetMul(CreateRange(-10, -2), CreateRange(-1, 1), false)); 433 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(2, 10), false)); 434 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-10, -2), false)); 435 ExpectEqual(Value(), GetMul(CreateRange(-1, 1), CreateRange(-1, 1), false)); 436 } 437 438 TEST_F(InductionVarRangeTest, GetDivMin) { 439 ExpectEqual(Value(-5), GetDiv(CreateRange(-10, 20), CreateConst(2), true)); 440 ExpectEqual(Value(-10), GetDiv(CreateRange(-10, 20), CreateConst(-2), true)); 441 ExpectEqual(Value(10), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), true)); 442 ExpectEqual(Value(-500), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), true)); 443 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), true)); 444 ExpectEqual(Value(-500), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), true)); 445 ExpectEqual(Value(10), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), true)); 446 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), true)); 447 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), true)); 448 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, -40), true)); 449 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), true)); 450 } 451 452 TEST_F(InductionVarRangeTest, GetDivMax) { 453 ExpectEqual(Value(10), GetDiv(CreateRange(-10, 20), CreateConst(2), false)); 454 ExpectEqual(Value(5), GetDiv(CreateRange(-10, 20), CreateConst(-2), false)); 455 ExpectEqual(Value(500), GetDiv(CreateRange(40, 1000), CreateRange(2, 4), false)); 456 ExpectEqual(Value(-10), GetDiv(CreateRange(40, 1000), CreateRange(-4, -2), false)); 457 ExpectEqual(Value(), GetDiv(CreateRange(40, 1000), CreateRange(-1, 1), false)); 458 ExpectEqual(Value(-10), GetDiv(CreateRange(-1000, -40), CreateRange(2, 4), false)); 459 ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false)); 460 ExpectEqual(Value(), GetDiv(CreateRange(-1000, -40), CreateRange(-1, 1), false)); 461 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(40, 1000), false)); 462 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1000, 40), false)); 463 ExpectEqual(Value(), GetDiv(CreateRange(-1, 1), CreateRange(-1, 1), false)); 464 } 465 466 TEST_F(InductionVarRangeTest, AddValue) { 467 ExpectEqual(Value(110), AddValue(Value(10), Value(100))); 468 ExpectEqual(Value(-5), AddValue(Value(x_, 1, -4), Value(x_, -1, -1))); 469 ExpectEqual(Value(x_, 3, -5), AddValue(Value(x_, 2, -4), Value(x_, 1, -1))); 470 ExpectEqual(Value(), AddValue(Value(x_, 1, 5), Value(y_, 1, -7))); 471 ExpectEqual(Value(x_, 1, 23), AddValue(Value(x_, 1, 20), Value(3))); 472 ExpectEqual(Value(y_, 1, 5), AddValue(Value(55), Value(y_, 1, -50))); 473 const int32_t max_value = std::numeric_limits<int32_t>::max(); 474 ExpectEqual(Value(max_value), AddValue(Value(max_value - 5), Value(5))); 475 ExpectEqual(Value(), AddValue(Value(max_value - 5), Value(6))); // unsafe 476 } 477 478 TEST_F(InductionVarRangeTest, SubValue) { 479 ExpectEqual(Value(-90), SubValue(Value(10), Value(100))); 480 ExpectEqual(Value(-3), SubValue(Value(x_, 1, -4), Value(x_, 1, -1))); 481 ExpectEqual(Value(x_, 2, -3), SubValue(Value(x_, 3, -4), Value(x_, 1, -1))); 482 ExpectEqual(Value(), SubValue(Value(x_, 1, 5), Value(y_, 1, -7))); 483 ExpectEqual(Value(x_, 1, 17), SubValue(Value(x_, 1, 20), Value(3))); 484 ExpectEqual(Value(y_, -4, 105), SubValue(Value(55), Value(y_, 4, -50))); 485 const int32_t min_value = std::numeric_limits<int32_t>::min(); 486 ExpectEqual(Value(min_value), SubValue(Value(min_value + 5), Value(5))); 487 ExpectEqual(Value(), SubValue(Value(min_value + 5), Value(6))); // unsafe 488 } 489 490 TEST_F(InductionVarRangeTest, MulValue) { 491 ExpectEqual(Value(1000), MulValue(Value(10), Value(100))); 492 ExpectEqual(Value(), MulValue(Value(x_, 1, -4), Value(x_, 1, -1))); 493 ExpectEqual(Value(), MulValue(Value(x_, 1, 5), Value(y_, 1, -7))); 494 ExpectEqual(Value(x_, 9, 60), MulValue(Value(x_, 3, 20), Value(3))); 495 ExpectEqual(Value(y_, 55, -110), MulValue(Value(55), Value(y_, 1, -2))); 496 ExpectEqual(Value(), MulValue(Value(90000), Value(-90000))); // unsafe 497 } 498 499 TEST_F(InductionVarRangeTest, MulValueSpecial) { 500 const int32_t min_value = std::numeric_limits<int32_t>::min(); 501 const int32_t max_value = std::numeric_limits<int32_t>::max(); 502 503 // Unsafe. 504 ExpectEqual(Value(), MulValue(Value(min_value), Value(min_value))); 505 ExpectEqual(Value(), MulValue(Value(min_value), Value(-1))); 506 ExpectEqual(Value(), MulValue(Value(min_value), Value(max_value))); 507 ExpectEqual(Value(), MulValue(Value(max_value), Value(max_value))); 508 509 // Safe. 510 ExpectEqual(Value(min_value), MulValue(Value(min_value), Value(1))); 511 ExpectEqual(Value(max_value), MulValue(Value(max_value), Value(1))); 512 ExpectEqual(Value(-max_value), MulValue(Value(max_value), Value(-1))); 513 ExpectEqual(Value(-1), MulValue(Value(1), Value(-1))); 514 ExpectEqual(Value(1), MulValue(Value(-1), Value(-1))); 515 } 516 517 TEST_F(InductionVarRangeTest, DivValue) { 518 ExpectEqual(Value(25), DivValue(Value(100), Value(4))); 519 ExpectEqual(Value(), DivValue(Value(x_, 1, -4), Value(x_, 1, -1))); 520 ExpectEqual(Value(), DivValue(Value(x_, 1, 5), Value(y_, 1, -7))); 521 ExpectEqual(Value(), DivValue(Value(x_, 12, 24), Value(3))); 522 ExpectEqual(Value(), DivValue(Value(55), Value(y_, 1, -50))); 523 ExpectEqual(Value(), DivValue(Value(1), Value(0))); // unsafe 524 } 525 526 TEST_F(InductionVarRangeTest, DivValueSpecial) { 527 const int32_t min_value = std::numeric_limits<int32_t>::min(); 528 const int32_t max_value = std::numeric_limits<int32_t>::max(); 529 530 // Unsafe. 531 ExpectEqual(Value(), DivValue(Value(min_value), Value(-1))); 532 533 // Safe. 534 ExpectEqual(Value(1), DivValue(Value(min_value), Value(min_value))); 535 ExpectEqual(Value(1), DivValue(Value(max_value), Value(max_value))); 536 ExpectEqual(Value(min_value), DivValue(Value(min_value), Value(1))); 537 ExpectEqual(Value(max_value), DivValue(Value(max_value), Value(1))); 538 ExpectEqual(Value(-max_value), DivValue(Value(max_value), Value(-1))); 539 ExpectEqual(Value(-1), DivValue(Value(1), Value(-1))); 540 ExpectEqual(Value(1), DivValue(Value(-1), Value(-1))); 541 } 542 543 TEST_F(InductionVarRangeTest, MinValue) { 544 ExpectEqual(Value(10), MinValue(Value(10), Value(100))); 545 ExpectEqual(Value(x_, 1, -4), MinValue(Value(x_, 1, -4), Value(x_, 1, -1))); 546 ExpectEqual(Value(x_, 4, -4), MinValue(Value(x_, 4, -4), Value(x_, 4, -1))); 547 ExpectEqual(Value(), MinValue(Value(x_, 1, 5), Value(y_, 1, -7))); 548 ExpectEqual(Value(), MinValue(Value(x_, 1, 20), Value(3))); 549 ExpectEqual(Value(), MinValue(Value(55), Value(y_, 1, -50))); 550 } 551 552 TEST_F(InductionVarRangeTest, MaxValue) { 553 ExpectEqual(Value(100), MaxValue(Value(10), Value(100))); 554 ExpectEqual(Value(x_, 1, -1), MaxValue(Value(x_, 1, -4), Value(x_, 1, -1))); 555 ExpectEqual(Value(x_, 4, -1), MaxValue(Value(x_, 4, -4), Value(x_, 4, -1))); 556 ExpectEqual(Value(), MaxValue(Value(x_, 1, 5), Value(y_, 1, -7))); 557 ExpectEqual(Value(), MaxValue(Value(x_, 1, 20), Value(3))); 558 ExpectEqual(Value(), MaxValue(Value(55), Value(y_, 1, -50))); 559 } 560 561 // 562 // Tests on public methods. 563 // 564 565 TEST_F(InductionVarRangeTest, ConstantTripCountUp) { 566 BuildLoop(0, graph_->GetIntConstant(1000), 1); 567 PerformInductionVarAnalysis(); 568 569 Value v1, v2; 570 bool needs_finite_test = true; 571 572 // In context of header: known. 573 range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); 574 EXPECT_FALSE(needs_finite_test); 575 ExpectEqual(Value(0), v1); 576 ExpectEqual(Value(1000), v2); 577 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 578 579 // In context of loop-body: known. 580 range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); 581 EXPECT_FALSE(needs_finite_test); 582 ExpectEqual(Value(0), v1); 583 ExpectEqual(Value(999), v2); 584 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 585 range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); 586 EXPECT_FALSE(needs_finite_test); 587 ExpectEqual(Value(1), v1); 588 ExpectEqual(Value(1000), v2); 589 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 590 } 591 592 TEST_F(InductionVarRangeTest, ConstantTripCountDown) { 593 BuildLoop(1000, graph_->GetIntConstant(0), -1); 594 PerformInductionVarAnalysis(); 595 596 Value v1, v2; 597 bool needs_finite_test = true; 598 599 // In context of header: known. 600 range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); 601 EXPECT_FALSE(needs_finite_test); 602 ExpectEqual(Value(0), v1); 603 ExpectEqual(Value(1000), v2); 604 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 605 606 // In context of loop-body: known. 607 range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); 608 EXPECT_FALSE(needs_finite_test); 609 ExpectEqual(Value(1), v1); 610 ExpectEqual(Value(1000), v2); 611 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 612 range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); 613 EXPECT_FALSE(needs_finite_test); 614 ExpectEqual(Value(0), v1); 615 ExpectEqual(Value(999), v2); 616 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 617 } 618 619 TEST_F(InductionVarRangeTest, SymbolicTripCountUp) { 620 BuildLoop(0, x_, 1); 621 PerformInductionVarAnalysis(); 622 623 Value v1, v2; 624 bool needs_finite_test = true; 625 bool needs_taken_test = true; 626 627 // In context of header: upper unknown. 628 range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); 629 EXPECT_FALSE(needs_finite_test); 630 ExpectEqual(Value(0), v1); 631 ExpectEqual(Value(), v2); 632 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 633 634 // In context of loop-body: known. 635 range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); 636 EXPECT_FALSE(needs_finite_test); 637 ExpectEqual(Value(0), v1); 638 ExpectEqual(Value(x_, 1, -1), v2); 639 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 640 range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); 641 EXPECT_FALSE(needs_finite_test); 642 ExpectEqual(Value(1), v1); 643 ExpectEqual(Value(x_, 1, 0), v2); 644 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 645 646 HInstruction* lower = nullptr; 647 HInstruction* upper = nullptr; 648 HInstruction* taken = nullptr; 649 650 // Can generate code in context of loop-body only. 651 EXPECT_FALSE(range_.CanGenerateCode( 652 condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); 653 ASSERT_TRUE(range_.CanGenerateCode( 654 increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); 655 EXPECT_FALSE(needs_finite_test); 656 EXPECT_TRUE(needs_taken_test); 657 658 // Generates code. 659 range_.GenerateRangeCode( 660 increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper); 661 662 // Verify lower is 0+0. 663 ASSERT_TRUE(lower != nullptr); 664 ASSERT_TRUE(lower->IsAdd()); 665 ASSERT_TRUE(lower->InputAt(0)->IsIntConstant()); 666 EXPECT_EQ(0, lower->InputAt(0)->AsIntConstant()->GetValue()); 667 ASSERT_TRUE(lower->InputAt(1)->IsIntConstant()); 668 EXPECT_EQ(0, lower->InputAt(1)->AsIntConstant()->GetValue()); 669 670 // Verify upper is (V-1)+0. 671 ASSERT_TRUE(upper != nullptr); 672 ASSERT_TRUE(upper->IsAdd()); 673 ASSERT_TRUE(upper->InputAt(0)->IsSub()); 674 EXPECT_TRUE(upper->InputAt(0)->InputAt(0)->IsParameterValue()); 675 ASSERT_TRUE(upper->InputAt(0)->InputAt(1)->IsIntConstant()); 676 EXPECT_EQ(1, upper->InputAt(0)->InputAt(1)->AsIntConstant()->GetValue()); 677 ASSERT_TRUE(upper->InputAt(1)->IsIntConstant()); 678 EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue()); 679 680 // Verify taken-test is 0<V. 681 range_.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken); 682 ASSERT_TRUE(taken != nullptr); 683 ASSERT_TRUE(taken->IsLessThan()); 684 ASSERT_TRUE(taken->InputAt(0)->IsIntConstant()); 685 EXPECT_EQ(0, taken->InputAt(0)->AsIntConstant()->GetValue()); 686 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); 687 } 688 689 TEST_F(InductionVarRangeTest, SymbolicTripCountDown) { 690 BuildLoop(1000, x_, -1); 691 PerformInductionVarAnalysis(); 692 693 Value v1, v2; 694 bool needs_finite_test = true; 695 bool needs_taken_test = true; 696 697 // In context of header: lower unknown. 698 range_.GetInductionRange(condition_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); 699 EXPECT_FALSE(needs_finite_test); 700 ExpectEqual(Value(), v1); 701 ExpectEqual(Value(1000), v2); 702 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 703 704 // In context of loop-body: known. 705 range_.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test); 706 EXPECT_FALSE(needs_finite_test); 707 ExpectEqual(Value(x_, 1, 1), v1); 708 ExpectEqual(Value(1000), v2); 709 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 710 range_.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test); 711 EXPECT_FALSE(needs_finite_test); 712 ExpectEqual(Value(x_, 1, 0), v1); 713 ExpectEqual(Value(999), v2); 714 EXPECT_FALSE(range_.RefineOuter(&v1, &v2)); 715 716 HInstruction* lower = nullptr; 717 HInstruction* upper = nullptr; 718 HInstruction* taken = nullptr; 719 720 // Can generate code in context of loop-body only. 721 EXPECT_FALSE(range_.CanGenerateCode( 722 condition_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); 723 ASSERT_TRUE(range_.CanGenerateCode( 724 increment_, condition_->InputAt(0), &needs_finite_test, &needs_taken_test)); 725 EXPECT_FALSE(needs_finite_test); 726 EXPECT_TRUE(needs_taken_test); 727 728 // Generates code. 729 range_.GenerateRangeCode( 730 increment_, condition_->InputAt(0), graph_, loop_preheader_, &lower, &upper); 731 732 // Verify lower is 1000-((1000-V)-1). 733 ASSERT_TRUE(lower != nullptr); 734 ASSERT_TRUE(lower->IsSub()); 735 ASSERT_TRUE(lower->InputAt(0)->IsIntConstant()); 736 EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue()); 737 lower = lower->InputAt(1); 738 ASSERT_TRUE(lower->IsSub()); 739 ASSERT_TRUE(lower->InputAt(1)->IsIntConstant()); 740 EXPECT_EQ(1, lower->InputAt(1)->AsIntConstant()->GetValue()); 741 lower = lower->InputAt(0); 742 ASSERT_TRUE(lower->IsSub()); 743 ASSERT_TRUE(lower->InputAt(0)->IsIntConstant()); 744 EXPECT_EQ(1000, lower->InputAt(0)->AsIntConstant()->GetValue()); 745 EXPECT_TRUE(lower->InputAt(1)->IsParameterValue()); 746 747 // Verify upper is 1000-0. 748 ASSERT_TRUE(upper != nullptr); 749 ASSERT_TRUE(upper->IsSub()); 750 ASSERT_TRUE(upper->InputAt(0)->IsIntConstant()); 751 EXPECT_EQ(1000, upper->InputAt(0)->AsIntConstant()->GetValue()); 752 ASSERT_TRUE(upper->InputAt(1)->IsIntConstant()); 753 EXPECT_EQ(0, upper->InputAt(1)->AsIntConstant()->GetValue()); 754 755 // Verify taken-test is 1000>V. 756 range_.GenerateTakenTest(increment_, graph_, loop_preheader_, &taken); 757 ASSERT_TRUE(taken != nullptr); 758 ASSERT_TRUE(taken->IsGreaterThan()); 759 ASSERT_TRUE(taken->InputAt(0)->IsIntConstant()); 760 EXPECT_EQ(1000, taken->InputAt(0)->AsIntConstant()->GetValue()); 761 EXPECT_TRUE(taken->InputAt(1)->IsParameterValue()); 762 } 763 764 } // namespace art 765
