1 /* 2 * Copyright (C) 2017 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 "load_store_analysis.h" 18 #include "nodes.h" 19 #include "optimizing_unit_test.h" 20 21 #include "gtest/gtest.h" 22 23 namespace art { 24 25 class LoadStoreAnalysisTest : public OptimizingUnitTest { 26 public: 27 LoadStoreAnalysisTest() : graph_(CreateGraph()) { } 28 29 HGraph* graph_; 30 }; 31 32 TEST_F(LoadStoreAnalysisTest, ArrayHeapLocations) { 33 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 34 graph_->AddBlock(entry); 35 graph_->SetEntryBlock(entry); 36 37 // entry: 38 // array ParameterValue 39 // index ParameterValue 40 // c1 IntConstant 41 // c2 IntConstant 42 // c3 IntConstant 43 // array_get1 ArrayGet [array, c1] 44 // array_get2 ArrayGet [array, c2] 45 // array_set1 ArraySet [array, c1, c3] 46 // array_set2 ArraySet [array, index, c3] 47 HInstruction* array = new (GetAllocator()) HParameterValue( 48 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); 49 HInstruction* index = new (GetAllocator()) HParameterValue( 50 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32); 51 HInstruction* c1 = graph_->GetIntConstant(1); 52 HInstruction* c2 = graph_->GetIntConstant(2); 53 HInstruction* c3 = graph_->GetIntConstant(3); 54 HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array, c1, DataType::Type::kInt32, 0); 55 HInstruction* array_get2 = new (GetAllocator()) HArrayGet(array, c2, DataType::Type::kInt32, 0); 56 HInstruction* array_set1 = 57 new (GetAllocator()) HArraySet(array, c1, c3, DataType::Type::kInt32, 0); 58 HInstruction* array_set2 = 59 new (GetAllocator()) HArraySet(array, index, c3, DataType::Type::kInt32, 0); 60 entry->AddInstruction(array); 61 entry->AddInstruction(index); 62 entry->AddInstruction(array_get1); 63 entry->AddInstruction(array_get2); 64 entry->AddInstruction(array_set1); 65 entry->AddInstruction(array_set2); 66 67 // Test HeapLocationCollector initialization. 68 // Should be no heap locations, no operations on the heap. 69 HeapLocationCollector heap_location_collector(graph_); 70 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U); 71 ASSERT_FALSE(heap_location_collector.HasHeapStores()); 72 73 // Test that after visiting the graph_, it must see following heap locations 74 // array[c1], array[c2], array[index]; and it should see heap stores. 75 heap_location_collector.VisitBasicBlock(entry); 76 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 3U); 77 ASSERT_TRUE(heap_location_collector.HasHeapStores()); 78 79 // Test queries on HeapLocationCollector's ref info and index records. 80 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(array); 81 DataType::Type type = DataType::Type::kInt32; 82 size_t field = HeapLocation::kInvalidFieldOffset; 83 size_t vec = HeapLocation::kScalar; 84 size_t class_def = HeapLocation::kDeclaringClassDefIndexForArrays; 85 size_t loc1 = heap_location_collector.FindHeapLocationIndex( 86 ref, type, field, c1, vec, class_def); 87 size_t loc2 = heap_location_collector.FindHeapLocationIndex( 88 ref, type, field, c2, vec, class_def); 89 size_t loc3 = heap_location_collector.FindHeapLocationIndex( 90 ref, type, field, index, vec, class_def); 91 // must find this reference info for array in HeapLocationCollector. 92 ASSERT_TRUE(ref != nullptr); 93 // must find these heap locations; 94 // and array[1], array[2], array[3] should be different heap locations. 95 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound); 96 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound); 97 ASSERT_TRUE(loc3 != HeapLocationCollector::kHeapLocationNotFound); 98 ASSERT_TRUE(loc1 != loc2); 99 ASSERT_TRUE(loc2 != loc3); 100 ASSERT_TRUE(loc1 != loc3); 101 102 // Test alias relationships after building aliasing matrix. 103 // array[1] and array[2] clearly should not alias; 104 // array[index] should alias with the others, because index is an unknow value. 105 heap_location_collector.BuildAliasingMatrix(); 106 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 107 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3)); 108 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc3)); 109 } 110 111 TEST_F(LoadStoreAnalysisTest, FieldHeapLocations) { 112 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 113 graph_->AddBlock(entry); 114 graph_->SetEntryBlock(entry); 115 116 // entry: 117 // object ParameterValue 118 // c1 IntConstant 119 // set_field10 InstanceFieldSet [object, c1, 10] 120 // get_field10 InstanceFieldGet [object, 10] 121 // get_field20 InstanceFieldGet [object, 20] 122 123 HInstruction* c1 = graph_->GetIntConstant(1); 124 HInstruction* object = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 125 dex::TypeIndex(0), 126 0, 127 DataType::Type::kReference); 128 HInstanceFieldSet* set_field10 = new (GetAllocator()) HInstanceFieldSet(object, 129 c1, 130 nullptr, 131 DataType::Type::kInt32, 132 MemberOffset(10), 133 false, 134 kUnknownFieldIndex, 135 kUnknownClassDefIndex, 136 graph_->GetDexFile(), 137 0); 138 HInstanceFieldGet* get_field10 = new (GetAllocator()) HInstanceFieldGet(object, 139 nullptr, 140 DataType::Type::kInt32, 141 MemberOffset(10), 142 false, 143 kUnknownFieldIndex, 144 kUnknownClassDefIndex, 145 graph_->GetDexFile(), 146 0); 147 HInstanceFieldGet* get_field20 = new (GetAllocator()) HInstanceFieldGet(object, 148 nullptr, 149 DataType::Type::kInt32, 150 MemberOffset(20), 151 false, 152 kUnknownFieldIndex, 153 kUnknownClassDefIndex, 154 graph_->GetDexFile(), 155 0); 156 entry->AddInstruction(object); 157 entry->AddInstruction(set_field10); 158 entry->AddInstruction(get_field10); 159 entry->AddInstruction(get_field20); 160 161 // Test HeapLocationCollector initialization. 162 // Should be no heap locations, no operations on the heap. 163 HeapLocationCollector heap_location_collector(graph_); 164 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 0U); 165 ASSERT_FALSE(heap_location_collector.HasHeapStores()); 166 167 // Test that after visiting the graph, it must see following heap locations 168 // object.field10, object.field20 and it should see heap stores. 169 heap_location_collector.VisitBasicBlock(entry); 170 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 2U); 171 ASSERT_TRUE(heap_location_collector.HasHeapStores()); 172 173 // Test queries on HeapLocationCollector's ref info and index records. 174 ReferenceInfo* ref = heap_location_collector.FindReferenceInfoOf(object); 175 size_t loc1 = heap_location_collector.GetFieldHeapLocation(object, &get_field10->GetFieldInfo()); 176 size_t loc2 = heap_location_collector.GetFieldHeapLocation(object, &get_field20->GetFieldInfo()); 177 // must find references info for object and in HeapLocationCollector. 178 ASSERT_TRUE(ref != nullptr); 179 // must find these heap locations. 180 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound); 181 ASSERT_TRUE(loc2 != HeapLocationCollector::kHeapLocationNotFound); 182 // different fields of same object. 183 ASSERT_TRUE(loc1 != loc2); 184 // accesses to different fields of the same object should not alias. 185 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 186 } 187 188 TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) { 189 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 190 graph_->AddBlock(entry); 191 graph_->SetEntryBlock(entry); 192 graph_->BuildDominatorTree(); 193 194 HInstruction* array = new (GetAllocator()) HParameterValue( 195 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); 196 HInstruction* index = new (GetAllocator()) HParameterValue( 197 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32); 198 HInstruction* c0 = graph_->GetIntConstant(0); 199 HInstruction* c1 = graph_->GetIntConstant(1); 200 HInstruction* c_neg1 = graph_->GetIntConstant(-1); 201 HInstruction* add0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0); 202 HInstruction* add1 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c1); 203 HInstruction* sub0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0); 204 HInstruction* sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c1); 205 HInstruction* sub_neg1 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c_neg1); 206 HInstruction* rev_sub1 = new (GetAllocator()) HSub(DataType::Type::kInt32, c1, index); 207 HInstruction* arr_set1 = new (GetAllocator()) HArraySet(array, c0, c0, DataType::Type::kInt32, 0); 208 HInstruction* arr_set2 = new (GetAllocator()) HArraySet(array, c1, c0, DataType::Type::kInt32, 0); 209 HInstruction* arr_set3 = 210 new (GetAllocator()) HArraySet(array, add0, c0, DataType::Type::kInt32, 0); 211 HInstruction* arr_set4 = 212 new (GetAllocator()) HArraySet(array, add1, c0, DataType::Type::kInt32, 0); 213 HInstruction* arr_set5 = 214 new (GetAllocator()) HArraySet(array, sub0, c0, DataType::Type::kInt32, 0); 215 HInstruction* arr_set6 = 216 new (GetAllocator()) HArraySet(array, sub1, c0, DataType::Type::kInt32, 0); 217 HInstruction* arr_set7 = 218 new (GetAllocator()) HArraySet(array, rev_sub1, c0, DataType::Type::kInt32, 0); 219 HInstruction* arr_set8 = 220 new (GetAllocator()) HArraySet(array, sub_neg1, c0, DataType::Type::kInt32, 0); 221 222 entry->AddInstruction(array); 223 entry->AddInstruction(index); 224 entry->AddInstruction(add0); 225 entry->AddInstruction(add1); 226 entry->AddInstruction(sub0); 227 entry->AddInstruction(sub1); 228 entry->AddInstruction(sub_neg1); 229 entry->AddInstruction(rev_sub1); 230 231 entry->AddInstruction(arr_set1); // array[0] = c0 232 entry->AddInstruction(arr_set2); // array[1] = c0 233 entry->AddInstruction(arr_set3); // array[i+0] = c0 234 entry->AddInstruction(arr_set4); // array[i+1] = c0 235 entry->AddInstruction(arr_set5); // array[i-0] = c0 236 entry->AddInstruction(arr_set6); // array[i-1] = c0 237 entry->AddInstruction(arr_set7); // array[1-i] = c0 238 entry->AddInstruction(arr_set8); // array[i-(-1)] = c0 239 240 LoadStoreAnalysis lsa(graph_); 241 lsa.Run(); 242 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector(); 243 244 // LSA/HeapLocationCollector should see those ArrayGet instructions. 245 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U); 246 ASSERT_TRUE(heap_location_collector.HasHeapStores()); 247 248 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis. 249 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound; 250 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound; 251 252 // Test alias: array[0] and array[1] 253 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set1); 254 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set2); 255 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 256 257 // Test alias: array[i+0] and array[i-0] 258 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set3); 259 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set5); 260 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 261 262 // Test alias: array[i+1] and array[i-1] 263 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4); 264 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set6); 265 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 266 267 // Test alias: array[i+1] and array[1-i] 268 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4); 269 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set7); 270 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 271 272 // Test alias: array[i+1] and array[i-(-1)] 273 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set4); 274 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set8); 275 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 276 } 277 278 TEST_F(LoadStoreAnalysisTest, ArrayAliasingTest) { 279 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 280 graph_->AddBlock(entry); 281 graph_->SetEntryBlock(entry); 282 graph_->BuildDominatorTree(); 283 284 HInstruction* array = new (GetAllocator()) HParameterValue( 285 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); 286 HInstruction* index = new (GetAllocator()) HParameterValue( 287 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32); 288 HInstruction* c0 = graph_->GetIntConstant(0); 289 HInstruction* c1 = graph_->GetIntConstant(1); 290 HInstruction* c6 = graph_->GetIntConstant(6); 291 HInstruction* c8 = graph_->GetIntConstant(8); 292 293 HInstruction* arr_set_0 = new (GetAllocator()) HArraySet(array, 294 c0, 295 c0, 296 DataType::Type::kInt32, 297 0); 298 HInstruction* arr_set_1 = new (GetAllocator()) HArraySet(array, 299 c1, 300 c0, 301 DataType::Type::kInt32, 302 0); 303 HInstruction* arr_set_i = new (GetAllocator()) HArraySet(array, 304 index, 305 c0, 306 DataType::Type::kInt32, 307 0); 308 309 HVecOperation* v1 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(), 310 c1, 311 DataType::Type::kInt32, 312 4, 313 kNoDexPc); 314 HVecOperation* v2 = new (GetAllocator()) HVecReplicateScalar(GetAllocator(), 315 c1, 316 DataType::Type::kInt32, 317 2, 318 kNoDexPc); 319 HInstruction* i_add6 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c6); 320 HInstruction* i_add8 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c8); 321 322 HInstruction* vstore_0 = new (GetAllocator()) HVecStore( 323 GetAllocator(), 324 array, 325 c0, 326 v1, 327 DataType::Type::kInt32, 328 SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 329 4, 330 kNoDexPc); 331 HInstruction* vstore_1 = new (GetAllocator()) HVecStore( 332 GetAllocator(), 333 array, 334 c1, 335 v1, 336 DataType::Type::kInt32, 337 SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 338 4, 339 kNoDexPc); 340 HInstruction* vstore_8 = new (GetAllocator()) HVecStore( 341 GetAllocator(), 342 array, 343 c8, 344 v1, 345 DataType::Type::kInt32, 346 SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 347 4, 348 kNoDexPc); 349 HInstruction* vstore_i = new (GetAllocator()) HVecStore( 350 GetAllocator(), 351 array, 352 index, 353 v1, 354 DataType::Type::kInt32, 355 SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 356 4, 357 kNoDexPc); 358 HInstruction* vstore_i_add6 = new (GetAllocator()) HVecStore( 359 GetAllocator(), 360 array, 361 i_add6, 362 v1, 363 DataType::Type::kInt32, 364 SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 365 4, 366 kNoDexPc); 367 HInstruction* vstore_i_add8 = new (GetAllocator()) HVecStore( 368 GetAllocator(), 369 array, 370 i_add8, 371 v1, 372 DataType::Type::kInt32, 373 SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 374 4, 375 kNoDexPc); 376 HInstruction* vstore_i_add6_vlen2 = new (GetAllocator()) HVecStore( 377 GetAllocator(), 378 array, 379 i_add6, 380 v2, 381 DataType::Type::kInt32, 382 SideEffects::ArrayWriteOfType(DataType::Type::kInt32), 383 2, 384 kNoDexPc); 385 386 entry->AddInstruction(array); 387 entry->AddInstruction(index); 388 389 entry->AddInstruction(arr_set_0); 390 entry->AddInstruction(arr_set_1); 391 entry->AddInstruction(arr_set_i); 392 entry->AddInstruction(v1); 393 entry->AddInstruction(v2); 394 entry->AddInstruction(i_add6); 395 entry->AddInstruction(i_add8); 396 entry->AddInstruction(vstore_0); 397 entry->AddInstruction(vstore_1); 398 entry->AddInstruction(vstore_8); 399 entry->AddInstruction(vstore_i); 400 entry->AddInstruction(vstore_i_add6); 401 entry->AddInstruction(vstore_i_add8); 402 entry->AddInstruction(vstore_i_add6_vlen2); 403 404 LoadStoreAnalysis lsa(graph_); 405 lsa.Run(); 406 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector(); 407 408 // LSA/HeapLocationCollector should see those instructions. 409 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 10U); 410 ASSERT_TRUE(heap_location_collector.HasHeapStores()); 411 412 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis. 413 size_t loc1, loc2; 414 415 // Test alias: array[0] and array[0,1,2,3] 416 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0); 417 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0); 418 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 419 420 // Test alias: array[0] and array[1,2,3,4] 421 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0); 422 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1); 423 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 424 425 // Test alias: array[0] and array[8,9,10,11] 426 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0); 427 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8); 428 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 429 430 // Test alias: array[1] and array[8,9,10,11] 431 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1); 432 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8); 433 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 434 435 // Test alias: array[1] and array[0,1,2,3] 436 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1); 437 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0); 438 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 439 440 // Test alias: array[0,1,2,3] and array[8,9,10,11] 441 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0); 442 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_8); 443 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 444 445 // Test alias: array[0,1,2,3] and array[1,2,3,4] 446 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_0); 447 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_1); 448 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 449 450 // Test alias: array[0] and array[i,i+1,i+2,i+3] 451 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_0); 452 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i); 453 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 454 455 // Test alias: array[i] and array[0,1,2,3] 456 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i); 457 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_0); 458 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 459 460 // Test alias: array[i] and array[i,i+1,i+2,i+3] 461 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i); 462 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i); 463 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 464 465 // Test alias: array[i] and array[i+8,i+9,i+10,i+11] 466 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_i); 467 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8); 468 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 469 470 // Test alias: array[i+6,i+7,i+8,i+9] and array[i+8,i+9,i+10,i+11] 471 // Test partial overlap. 472 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6); 473 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8); 474 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 475 476 // Test alias: array[i+6,i+7] and array[i,i+1,i+2,i+3] 477 // Test different vector lengths. 478 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2); 479 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i); 480 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 481 482 // Test alias: array[i+6,i+7] and array[i+8,i+9,i+10,i+11] 483 loc1 = heap_location_collector.GetArrayHeapLocation(vstore_i_add6_vlen2); 484 loc2 = heap_location_collector.GetArrayHeapLocation(vstore_i_add8); 485 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 486 } 487 488 TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) { 489 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 490 graph_->AddBlock(entry); 491 graph_->SetEntryBlock(entry); 492 graph_->BuildDominatorTree(); 493 494 HInstruction* array = new (GetAllocator()) HParameterValue( 495 graph_->GetDexFile(), dex::TypeIndex(0), 0, DataType::Type::kReference); 496 HInstruction* index = new (GetAllocator()) HParameterValue( 497 graph_->GetDexFile(), dex::TypeIndex(1), 1, DataType::Type::kInt32); 498 499 HInstruction* c0 = graph_->GetIntConstant(0); 500 HInstruction* c_0x80000000 = graph_->GetIntConstant(0x80000000); 501 HInstruction* c_0x10 = graph_->GetIntConstant(0x10); 502 HInstruction* c_0xFFFFFFF0 = graph_->GetIntConstant(0xFFFFFFF0); 503 HInstruction* c_0x7FFFFFFF = graph_->GetIntConstant(0x7FFFFFFF); 504 HInstruction* c_0x80000001 = graph_->GetIntConstant(0x80000001); 505 506 // `index+0x80000000` and `index-0x80000000` array indices MAY alias. 507 HInstruction* add_0x80000000 = new (GetAllocator()) HAdd( 508 DataType::Type::kInt32, index, c_0x80000000); 509 HInstruction* sub_0x80000000 = new (GetAllocator()) HSub( 510 DataType::Type::kInt32, index, c_0x80000000); 511 HInstruction* arr_set_1 = new (GetAllocator()) HArraySet( 512 array, add_0x80000000, c0, DataType::Type::kInt32, 0); 513 HInstruction* arr_set_2 = new (GetAllocator()) HArraySet( 514 array, sub_0x80000000, c0, DataType::Type::kInt32, 0); 515 516 // `index+0x10` and `index-0xFFFFFFF0` array indices MAY alias. 517 HInstruction* add_0x10 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c_0x10); 518 HInstruction* sub_0xFFFFFFF0 = new (GetAllocator()) HSub( 519 DataType::Type::kInt32, index, c_0xFFFFFFF0); 520 HInstruction* arr_set_3 = new (GetAllocator()) HArraySet( 521 array, add_0x10, c0, DataType::Type::kInt32, 0); 522 HInstruction* arr_set_4 = new (GetAllocator()) HArraySet( 523 array, sub_0xFFFFFFF0, c0, DataType::Type::kInt32, 0); 524 525 // `index+0x7FFFFFFF` and `index-0x80000001` array indices MAY alias. 526 HInstruction* add_0x7FFFFFFF = new (GetAllocator()) HAdd( 527 DataType::Type::kInt32, index, c_0x7FFFFFFF); 528 HInstruction* sub_0x80000001 = new (GetAllocator()) HSub( 529 DataType::Type::kInt32, index, c_0x80000001); 530 HInstruction* arr_set_5 = new (GetAllocator()) HArraySet( 531 array, add_0x7FFFFFFF, c0, DataType::Type::kInt32, 0); 532 HInstruction* arr_set_6 = new (GetAllocator()) HArraySet( 533 array, sub_0x80000001, c0, DataType::Type::kInt32, 0); 534 535 // `index+0` and `index-0` array indices MAY alias. 536 HInstruction* add_0 = new (GetAllocator()) HAdd(DataType::Type::kInt32, index, c0); 537 HInstruction* sub_0 = new (GetAllocator()) HSub(DataType::Type::kInt32, index, c0); 538 HInstruction* arr_set_7 = new (GetAllocator()) HArraySet( 539 array, add_0, c0, DataType::Type::kInt32, 0); 540 HInstruction* arr_set_8 = new (GetAllocator()) HArraySet( 541 array, sub_0, c0, DataType::Type::kInt32, 0); 542 543 entry->AddInstruction(array); 544 entry->AddInstruction(index); 545 entry->AddInstruction(add_0x80000000); 546 entry->AddInstruction(sub_0x80000000); 547 entry->AddInstruction(add_0x10); 548 entry->AddInstruction(sub_0xFFFFFFF0); 549 entry->AddInstruction(add_0x7FFFFFFF); 550 entry->AddInstruction(sub_0x80000001); 551 entry->AddInstruction(add_0); 552 entry->AddInstruction(sub_0); 553 entry->AddInstruction(arr_set_1); 554 entry->AddInstruction(arr_set_2); 555 entry->AddInstruction(arr_set_3); 556 entry->AddInstruction(arr_set_4); 557 entry->AddInstruction(arr_set_5); 558 entry->AddInstruction(arr_set_6); 559 entry->AddInstruction(arr_set_7); 560 entry->AddInstruction(arr_set_8); 561 562 LoadStoreAnalysis lsa(graph_); 563 lsa.Run(); 564 const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector(); 565 566 // LSA/HeapLocationCollector should see those ArrayGet instructions. 567 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U); 568 ASSERT_TRUE(heap_location_collector.HasHeapStores()); 569 570 // Test queries on HeapLocationCollector's aliasing matrix after load store analysis. 571 size_t loc1 = HeapLocationCollector::kHeapLocationNotFound; 572 size_t loc2 = HeapLocationCollector::kHeapLocationNotFound; 573 574 // Test alias: array[i+0x80000000] and array[i-0x80000000] 575 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_1); 576 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2); 577 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 578 579 // Test alias: array[i+0x10] and array[i-0xFFFFFFF0] 580 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_3); 581 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_4); 582 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 583 584 // Test alias: array[i+0x7FFFFFFF] and array[i-0x80000001] 585 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_5); 586 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6); 587 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 588 589 // Test alias: array[i+0] and array[i-0] 590 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7); 591 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_8); 592 ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2)); 593 594 // Should not alias: 595 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_2); 596 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_6); 597 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 598 599 // Should not alias: 600 loc1 = heap_location_collector.GetArrayHeapLocation(arr_set_7); 601 loc2 = heap_location_collector.GetArrayHeapLocation(arr_set_2); 602 ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2)); 603 } 604 605 TEST_F(LoadStoreAnalysisTest, TestHuntOriginalRef) { 606 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph_); 607 graph_->AddBlock(entry); 608 graph_->SetEntryBlock(entry); 609 610 // Different ways where orignal array reference are transformed & passed to ArrayGet. 611 // ParameterValue --> ArrayGet 612 // ParameterValue --> BoundType --> ArrayGet 613 // ParameterValue --> BoundType --> NullCheck --> ArrayGet 614 // ParameterValue --> BoundType --> NullCheck --> IntermediateAddress --> ArrayGet 615 HInstruction* c1 = graph_->GetIntConstant(1); 616 HInstruction* array = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 617 dex::TypeIndex(0), 618 0, 619 DataType::Type::kReference); 620 HInstruction* array_get1 = new (GetAllocator()) HArrayGet(array, 621 c1, 622 DataType::Type::kInt32, 623 0); 624 625 HInstruction* bound_type = new (GetAllocator()) HBoundType(array); 626 HInstruction* array_get2 = new (GetAllocator()) HArrayGet(bound_type, 627 c1, 628 DataType::Type::kInt32, 629 0); 630 631 HInstruction* null_check = new (GetAllocator()) HNullCheck(bound_type, 0); 632 HInstruction* array_get3 = new (GetAllocator()) HArrayGet(null_check, 633 c1, 634 DataType::Type::kInt32, 635 0); 636 637 HInstruction* inter_addr = new (GetAllocator()) HIntermediateAddress(null_check, c1, 0); 638 HInstruction* array_get4 = new (GetAllocator()) HArrayGet(inter_addr, 639 c1, 640 DataType::Type::kInt32, 641 0); 642 entry->AddInstruction(array); 643 entry->AddInstruction(array_get1); 644 entry->AddInstruction(bound_type); 645 entry->AddInstruction(array_get2); 646 entry->AddInstruction(null_check); 647 entry->AddInstruction(array_get3); 648 entry->AddInstruction(inter_addr); 649 entry->AddInstruction(array_get4); 650 651 HeapLocationCollector heap_location_collector(graph_); 652 heap_location_collector.VisitBasicBlock(entry); 653 654 // Test that the HeapLocationCollector should be able to tell 655 // that there is only ONE array location, no matter how many 656 // times the original reference has been transformed by BoundType, 657 // NullCheck, IntermediateAddress, etc. 658 ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 1U); 659 size_t loc1 = heap_location_collector.GetArrayHeapLocation(array_get1); 660 size_t loc2 = heap_location_collector.GetArrayHeapLocation(array_get2); 661 size_t loc3 = heap_location_collector.GetArrayHeapLocation(array_get3); 662 size_t loc4 = heap_location_collector.GetArrayHeapLocation(array_get4); 663 ASSERT_TRUE(loc1 != HeapLocationCollector::kHeapLocationNotFound); 664 ASSERT_EQ(loc1, loc2); 665 ASSERT_EQ(loc1, loc3); 666 ASSERT_EQ(loc1, loc4); 667 } 668 669 } // namespace art 670
