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