1 /* 2 * Copyright (C) 2014 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 "bounds_check_elimination.h" 19 #include "builder.h" 20 #include "gvn.h" 21 #include "induction_var_analysis.h" 22 #include "instruction_simplifier.h" 23 #include "nodes.h" 24 #include "optimizing_unit_test.h" 25 #include "side_effects_analysis.h" 26 27 #include "gtest/gtest.h" 28 29 namespace art { 30 31 /** 32 * Fixture class for the BoundsCheckElimination tests. 33 */ 34 class BoundsCheckEliminationTest : public testing::Test { 35 public: 36 BoundsCheckEliminationTest() : pool_(), allocator_(&pool_) { 37 graph_ = CreateGraph(&allocator_); 38 graph_->SetHasBoundsChecks(true); 39 } 40 41 ~BoundsCheckEliminationTest() { } 42 43 void RunBCE() { 44 graph_->BuildDominatorTree(); 45 46 InstructionSimplifier(graph_, /* codegen */ nullptr, /* driver */ nullptr).Run(); 47 48 SideEffectsAnalysis side_effects(graph_); 49 side_effects.Run(); 50 51 GVNOptimization(graph_, side_effects).Run(); 52 53 HInductionVarAnalysis induction(graph_); 54 induction.Run(); 55 56 BoundsCheckElimination(graph_, side_effects, &induction).Run(); 57 } 58 59 ArenaPool pool_; 60 ArenaAllocator allocator_; 61 HGraph* graph_; 62 }; 63 64 65 // if (i < 0) { array[i] = 1; // Can't eliminate. } 66 // else if (i >= array.length) { array[i] = 1; // Can't eliminate. } 67 // else { array[i] = 1; // Can eliminate. } 68 TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) { 69 HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 70 graph_->AddBlock(entry); 71 graph_->SetEntryBlock(entry); 72 HInstruction* parameter1 = new (&allocator_) 73 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); // array 74 HInstruction* parameter2 = new (&allocator_) 75 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt); // i 76 entry->AddInstruction(parameter1); 77 entry->AddInstruction(parameter2); 78 79 HInstruction* constant_1 = graph_->GetIntConstant(1); 80 HInstruction* constant_0 = graph_->GetIntConstant(0); 81 82 HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_); 83 graph_->AddBlock(block1); 84 HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, constant_0); 85 HIf* if_inst = new (&allocator_) HIf(cmp); 86 block1->AddInstruction(cmp); 87 block1->AddInstruction(if_inst); 88 entry->AddSuccessor(block1); 89 90 HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_); 91 graph_->AddBlock(block2); 92 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0); 93 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 94 HBoundsCheck* bounds_check2 = new (&allocator_) 95 HBoundsCheck(parameter2, array_length, 0); 96 HArraySet* array_set = new (&allocator_) HArraySet( 97 null_check, bounds_check2, constant_1, Primitive::kPrimInt, 0); 98 block2->AddInstruction(null_check); 99 block2->AddInstruction(array_length); 100 block2->AddInstruction(bounds_check2); 101 block2->AddInstruction(array_set); 102 103 HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_); 104 graph_->AddBlock(block3); 105 null_check = new (&allocator_) HNullCheck(parameter1, 0); 106 array_length = new (&allocator_) HArrayLength(null_check, 0); 107 cmp = new (&allocator_) HLessThan(parameter2, array_length); 108 if_inst = new (&allocator_) HIf(cmp); 109 block3->AddInstruction(null_check); 110 block3->AddInstruction(array_length); 111 block3->AddInstruction(cmp); 112 block3->AddInstruction(if_inst); 113 114 HBasicBlock* block4 = new (&allocator_) HBasicBlock(graph_); 115 graph_->AddBlock(block4); 116 null_check = new (&allocator_) HNullCheck(parameter1, 0); 117 array_length = new (&allocator_) HArrayLength(null_check, 0); 118 HBoundsCheck* bounds_check4 = new (&allocator_) 119 HBoundsCheck(parameter2, array_length, 0); 120 array_set = new (&allocator_) HArraySet( 121 null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); 122 block4->AddInstruction(null_check); 123 block4->AddInstruction(array_length); 124 block4->AddInstruction(bounds_check4); 125 block4->AddInstruction(array_set); 126 127 HBasicBlock* block5 = new (&allocator_) HBasicBlock(graph_); 128 graph_->AddBlock(block5); 129 null_check = new (&allocator_) HNullCheck(parameter1, 0); 130 array_length = new (&allocator_) HArrayLength(null_check, 0); 131 HBoundsCheck* bounds_check5 = new (&allocator_) 132 HBoundsCheck(parameter2, array_length, 0); 133 array_set = new (&allocator_) HArraySet( 134 null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); 135 block5->AddInstruction(null_check); 136 block5->AddInstruction(array_length); 137 block5->AddInstruction(bounds_check5); 138 block5->AddInstruction(array_set); 139 140 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 141 graph_->AddBlock(exit); 142 block2->AddSuccessor(exit); 143 block4->AddSuccessor(exit); 144 block5->AddSuccessor(exit); 145 exit->AddInstruction(new (&allocator_) HExit()); 146 147 block1->AddSuccessor(block3); // True successor 148 block1->AddSuccessor(block2); // False successor 149 150 block3->AddSuccessor(block5); // True successor 151 block3->AddSuccessor(block4); // False successor 152 153 RunBCE(); 154 155 ASSERT_FALSE(IsRemoved(bounds_check2)); 156 ASSERT_FALSE(IsRemoved(bounds_check4)); 157 ASSERT_TRUE(IsRemoved(bounds_check5)); 158 } 159 160 // if (i > 0) { 161 // // Positive number plus MAX_INT will overflow and be negative. 162 // int j = i + Integer.MAX_VALUE; 163 // if (j < array.length) array[j] = 1; // Can't eliminate. 164 // } 165 TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) { 166 HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 167 graph_->AddBlock(entry); 168 graph_->SetEntryBlock(entry); 169 HInstruction* parameter1 = new (&allocator_) 170 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); // array 171 HInstruction* parameter2 = new (&allocator_) 172 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt); // i 173 entry->AddInstruction(parameter1); 174 entry->AddInstruction(parameter2); 175 176 HInstruction* constant_1 = graph_->GetIntConstant(1); 177 HInstruction* constant_0 = graph_->GetIntConstant(0); 178 HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX); 179 180 HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_); 181 graph_->AddBlock(block1); 182 HInstruction* cmp = new (&allocator_) HLessThanOrEqual(parameter2, constant_0); 183 HIf* if_inst = new (&allocator_) HIf(cmp); 184 block1->AddInstruction(cmp); 185 block1->AddInstruction(if_inst); 186 entry->AddSuccessor(block1); 187 188 HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_); 189 graph_->AddBlock(block2); 190 HInstruction* add = new (&allocator_) HAdd(Primitive::kPrimInt, parameter2, constant_max_int); 191 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0); 192 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 193 HInstruction* cmp2 = new (&allocator_) HGreaterThanOrEqual(add, array_length); 194 if_inst = new (&allocator_) HIf(cmp2); 195 block2->AddInstruction(add); 196 block2->AddInstruction(null_check); 197 block2->AddInstruction(array_length); 198 block2->AddInstruction(cmp2); 199 block2->AddInstruction(if_inst); 200 201 HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_); 202 graph_->AddBlock(block3); 203 HBoundsCheck* bounds_check = new (&allocator_) 204 HBoundsCheck(add, array_length, 0); 205 HArraySet* array_set = new (&allocator_) HArraySet( 206 null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); 207 block3->AddInstruction(bounds_check); 208 block3->AddInstruction(array_set); 209 210 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 211 graph_->AddBlock(exit); 212 exit->AddInstruction(new (&allocator_) HExit()); 213 block1->AddSuccessor(exit); // true successor 214 block1->AddSuccessor(block2); // false successor 215 block2->AddSuccessor(exit); // true successor 216 block2->AddSuccessor(block3); // false successor 217 block3->AddSuccessor(exit); 218 219 RunBCE(); 220 221 ASSERT_FALSE(IsRemoved(bounds_check)); 222 } 223 224 // if (i < array.length) { 225 // int j = i - Integer.MAX_VALUE; 226 // j = j - Integer.MAX_VALUE; // j is (i+2) after subtracting MAX_INT twice 227 // if (j > 0) array[j] = 1; // Can't eliminate. 228 // } 229 TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) { 230 HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 231 graph_->AddBlock(entry); 232 graph_->SetEntryBlock(entry); 233 HInstruction* parameter1 = new (&allocator_) 234 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); // array 235 HInstruction* parameter2 = new (&allocator_) 236 HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt); // i 237 entry->AddInstruction(parameter1); 238 entry->AddInstruction(parameter2); 239 240 HInstruction* constant_1 = graph_->GetIntConstant(1); 241 HInstruction* constant_0 = graph_->GetIntConstant(0); 242 HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX); 243 244 HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_); 245 graph_->AddBlock(block1); 246 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0); 247 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 248 HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, array_length); 249 HIf* if_inst = new (&allocator_) HIf(cmp); 250 block1->AddInstruction(null_check); 251 block1->AddInstruction(array_length); 252 block1->AddInstruction(cmp); 253 block1->AddInstruction(if_inst); 254 entry->AddSuccessor(block1); 255 256 HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_); 257 graph_->AddBlock(block2); 258 HInstruction* sub1 = new (&allocator_) HSub(Primitive::kPrimInt, parameter2, constant_max_int); 259 HInstruction* sub2 = new (&allocator_) HSub(Primitive::kPrimInt, sub1, constant_max_int); 260 HInstruction* cmp2 = new (&allocator_) HLessThanOrEqual(sub2, constant_0); 261 if_inst = new (&allocator_) HIf(cmp2); 262 block2->AddInstruction(sub1); 263 block2->AddInstruction(sub2); 264 block2->AddInstruction(cmp2); 265 block2->AddInstruction(if_inst); 266 267 HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_); 268 graph_->AddBlock(block3); 269 HBoundsCheck* bounds_check = new (&allocator_) 270 HBoundsCheck(sub2, array_length, 0); 271 HArraySet* array_set = new (&allocator_) HArraySet( 272 null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); 273 block3->AddInstruction(bounds_check); 274 block3->AddInstruction(array_set); 275 276 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 277 graph_->AddBlock(exit); 278 exit->AddInstruction(new (&allocator_) HExit()); 279 block1->AddSuccessor(exit); // true successor 280 block1->AddSuccessor(block2); // false successor 281 block2->AddSuccessor(exit); // true successor 282 block2->AddSuccessor(block3); // false successor 283 block3->AddSuccessor(exit); 284 285 RunBCE(); 286 287 ASSERT_FALSE(IsRemoved(bounds_check)); 288 } 289 290 // array[6] = 1; // Can't eliminate. 291 // array[5] = 1; // Can eliminate. 292 // array[4] = 1; // Can eliminate. 293 TEST_F(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) { 294 HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 295 graph_->AddBlock(entry); 296 graph_->SetEntryBlock(entry); 297 HInstruction* parameter = new (&allocator_) HParameterValue( 298 graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); 299 entry->AddInstruction(parameter); 300 301 HInstruction* constant_5 = graph_->GetIntConstant(5); 302 HInstruction* constant_4 = graph_->GetIntConstant(4); 303 HInstruction* constant_6 = graph_->GetIntConstant(6); 304 HInstruction* constant_1 = graph_->GetIntConstant(1); 305 306 HBasicBlock* block = new (&allocator_) HBasicBlock(graph_); 307 graph_->AddBlock(block); 308 entry->AddSuccessor(block); 309 310 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0); 311 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 312 HBoundsCheck* bounds_check6 = new (&allocator_) 313 HBoundsCheck(constant_6, array_length, 0); 314 HInstruction* array_set = new (&allocator_) HArraySet( 315 null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0); 316 block->AddInstruction(null_check); 317 block->AddInstruction(array_length); 318 block->AddInstruction(bounds_check6); 319 block->AddInstruction(array_set); 320 321 null_check = new (&allocator_) HNullCheck(parameter, 0); 322 array_length = new (&allocator_) HArrayLength(null_check, 0); 323 HBoundsCheck* bounds_check5 = new (&allocator_) 324 HBoundsCheck(constant_5, array_length, 0); 325 array_set = new (&allocator_) HArraySet( 326 null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); 327 block->AddInstruction(null_check); 328 block->AddInstruction(array_length); 329 block->AddInstruction(bounds_check5); 330 block->AddInstruction(array_set); 331 332 null_check = new (&allocator_) HNullCheck(parameter, 0); 333 array_length = new (&allocator_) HArrayLength(null_check, 0); 334 HBoundsCheck* bounds_check4 = new (&allocator_) 335 HBoundsCheck(constant_4, array_length, 0); 336 array_set = new (&allocator_) HArraySet( 337 null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); 338 block->AddInstruction(null_check); 339 block->AddInstruction(array_length); 340 block->AddInstruction(bounds_check4); 341 block->AddInstruction(array_set); 342 343 block->AddInstruction(new (&allocator_) HGoto()); 344 345 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 346 graph_->AddBlock(exit); 347 block->AddSuccessor(exit); 348 exit->AddInstruction(new (&allocator_) HExit()); 349 350 RunBCE(); 351 352 ASSERT_FALSE(IsRemoved(bounds_check6)); 353 ASSERT_TRUE(IsRemoved(bounds_check5)); 354 ASSERT_TRUE(IsRemoved(bounds_check4)); 355 } 356 357 // for (int i=initial; i<array.length; i+=increment) { array[i] = 10; } 358 static HInstruction* BuildSSAGraph1(HGraph* graph, 359 ArenaAllocator* allocator, 360 int initial, 361 int increment, 362 IfCondition cond = kCondGE) { 363 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 364 graph->AddBlock(entry); 365 graph->SetEntryBlock(entry); 366 HInstruction* parameter = new (allocator) HParameterValue( 367 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); 368 entry->AddInstruction(parameter); 369 370 HInstruction* constant_initial = graph->GetIntConstant(initial); 371 HInstruction* constant_increment = graph->GetIntConstant(increment); 372 HInstruction* constant_10 = graph->GetIntConstant(10); 373 374 HBasicBlock* block = new (allocator) HBasicBlock(graph); 375 graph->AddBlock(block); 376 entry->AddSuccessor(block); 377 block->AddInstruction(new (allocator) HGoto()); 378 379 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 380 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 381 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 382 383 graph->AddBlock(loop_header); 384 graph->AddBlock(loop_body); 385 graph->AddBlock(exit); 386 block->AddSuccessor(loop_header); 387 loop_header->AddSuccessor(exit); // true successor 388 loop_header->AddSuccessor(loop_body); // false successor 389 loop_body->AddSuccessor(loop_header); 390 391 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 392 HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 393 HInstruction* array_length = new (allocator) HArrayLength(null_check, 0); 394 HInstruction* cmp = nullptr; 395 if (cond == kCondGE) { 396 cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 397 } else { 398 DCHECK(cond == kCondGT); 399 cmp = new (allocator) HGreaterThan(phi, array_length); 400 } 401 HInstruction* if_inst = new (allocator) HIf(cmp); 402 loop_header->AddPhi(phi); 403 loop_header->AddInstruction(null_check); 404 loop_header->AddInstruction(array_length); 405 loop_header->AddInstruction(cmp); 406 loop_header->AddInstruction(if_inst); 407 phi->AddInput(constant_initial); 408 409 null_check = new (allocator) HNullCheck(parameter, 0); 410 array_length = new (allocator) HArrayLength(null_check, 0); 411 HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 412 HInstruction* array_set = new (allocator) HArraySet( 413 null_check, bounds_check, constant_10, Primitive::kPrimInt, 0); 414 415 HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 416 loop_body->AddInstruction(null_check); 417 loop_body->AddInstruction(array_length); 418 loop_body->AddInstruction(bounds_check); 419 loop_body->AddInstruction(array_set); 420 loop_body->AddInstruction(add); 421 loop_body->AddInstruction(new (allocator) HGoto()); 422 phi->AddInput(add); 423 424 exit->AddInstruction(new (allocator) HExit()); 425 426 return bounds_check; 427 } 428 429 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1a) { 430 // for (int i=0; i<array.length; i++) { array[i] = 10; // Can eliminate with gvn. } 431 HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 1); 432 RunBCE(); 433 ASSERT_TRUE(IsRemoved(bounds_check)); 434 } 435 436 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1b) { 437 // for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. } 438 HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 1, 1); 439 RunBCE(); 440 ASSERT_TRUE(IsRemoved(bounds_check)); 441 } 442 443 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1c) { 444 // for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. } 445 HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, -1, 1); 446 RunBCE(); 447 ASSERT_FALSE(IsRemoved(bounds_check)); 448 } 449 450 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1d) { 451 // for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. } 452 HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 1, kCondGT); 453 RunBCE(); 454 ASSERT_FALSE(IsRemoved(bounds_check)); 455 } 456 457 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1e) { 458 // for (int i=0; i<array.length; i += 2) { 459 // array[i] = 10; // Can't eliminate due to overflow concern. } 460 HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 2); 461 RunBCE(); 462 ASSERT_FALSE(IsRemoved(bounds_check)); 463 } 464 465 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1f) { 466 // for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. } 467 HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 1, 2); 468 RunBCE(); 469 ASSERT_TRUE(IsRemoved(bounds_check)); 470 } 471 472 // for (int i=array.length; i>0; i+=increment) { array[i-1] = 10; } 473 static HInstruction* BuildSSAGraph2(HGraph *graph, 474 ArenaAllocator* allocator, 475 int initial, 476 int increment = -1, 477 IfCondition cond = kCondLE) { 478 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 479 graph->AddBlock(entry); 480 graph->SetEntryBlock(entry); 481 HInstruction* parameter = new (allocator) HParameterValue( 482 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); 483 entry->AddInstruction(parameter); 484 485 HInstruction* constant_initial = graph->GetIntConstant(initial); 486 HInstruction* constant_increment = graph->GetIntConstant(increment); 487 HInstruction* constant_minus_1 = graph->GetIntConstant(-1); 488 HInstruction* constant_10 = graph->GetIntConstant(10); 489 490 HBasicBlock* block = new (allocator) HBasicBlock(graph); 491 graph->AddBlock(block); 492 entry->AddSuccessor(block); 493 HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 494 HInstruction* array_length = new (allocator) HArrayLength(null_check, 0); 495 block->AddInstruction(null_check); 496 block->AddInstruction(array_length); 497 block->AddInstruction(new (allocator) HGoto()); 498 499 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 500 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 501 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 502 503 graph->AddBlock(loop_header); 504 graph->AddBlock(loop_body); 505 graph->AddBlock(exit); 506 block->AddSuccessor(loop_header); 507 loop_header->AddSuccessor(exit); // true successor 508 loop_header->AddSuccessor(loop_body); // false successor 509 loop_body->AddSuccessor(loop_header); 510 511 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 512 HInstruction* cmp = nullptr; 513 if (cond == kCondLE) { 514 cmp = new (allocator) HLessThanOrEqual(phi, constant_initial); 515 } else { 516 DCHECK(cond == kCondLT); 517 cmp = new (allocator) HLessThan(phi, constant_initial); 518 } 519 HInstruction* if_inst = new (allocator) HIf(cmp); 520 loop_header->AddPhi(phi); 521 loop_header->AddInstruction(cmp); 522 loop_header->AddInstruction(if_inst); 523 phi->AddInput(array_length); 524 525 HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1); 526 null_check = new (allocator) HNullCheck(parameter, 0); 527 array_length = new (allocator) HArrayLength(null_check, 0); 528 HInstruction* bounds_check = new (allocator) HBoundsCheck(add, array_length, 0); 529 HInstruction* array_set = new (allocator) HArraySet( 530 null_check, bounds_check, constant_10, Primitive::kPrimInt, 0); 531 HInstruction* add_phi = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 532 loop_body->AddInstruction(add); 533 loop_body->AddInstruction(null_check); 534 loop_body->AddInstruction(array_length); 535 loop_body->AddInstruction(bounds_check); 536 loop_body->AddInstruction(array_set); 537 loop_body->AddInstruction(add_phi); 538 loop_body->AddInstruction(new (allocator) HGoto()); 539 phi->AddInput(add); 540 541 exit->AddInstruction(new (allocator) HExit()); 542 543 return bounds_check; 544 } 545 546 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2a) { 547 // for (int i=array.length; i>0; i--) { array[i-1] = 10; // Can eliminate with gvn. } 548 HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0); 549 RunBCE(); 550 ASSERT_TRUE(IsRemoved(bounds_check)); 551 } 552 553 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2b) { 554 // for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. } 555 HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 1); 556 RunBCE(); 557 ASSERT_TRUE(IsRemoved(bounds_check)); 558 } 559 560 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2c) { 561 // for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. } 562 HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, -1); 563 RunBCE(); 564 ASSERT_FALSE(IsRemoved(bounds_check)); 565 } 566 567 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2d) { 568 // for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. } 569 HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0, -1, kCondLT); 570 RunBCE(); 571 ASSERT_FALSE(IsRemoved(bounds_check)); 572 } 573 574 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2e) { 575 // for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. } 576 HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0, -2); 577 RunBCE(); 578 ASSERT_TRUE(IsRemoved(bounds_check)); 579 } 580 581 // int[] array = new int[10]; 582 // for (int i=0; i<10; i+=increment) { array[i] = 10; } 583 static HInstruction* BuildSSAGraph3(HGraph* graph, 584 ArenaAllocator* allocator, 585 int initial, 586 int increment, 587 IfCondition cond) { 588 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 589 graph->AddBlock(entry); 590 graph->SetEntryBlock(entry); 591 592 HInstruction* constant_10 = graph->GetIntConstant(10); 593 HInstruction* constant_initial = graph->GetIntConstant(initial); 594 HInstruction* constant_increment = graph->GetIntConstant(increment); 595 596 HBasicBlock* block = new (allocator) HBasicBlock(graph); 597 graph->AddBlock(block); 598 entry->AddSuccessor(block); 599 // We pass a bogus constant for the class to avoid mocking one. 600 HInstruction* new_array = new (allocator) HNewArray( 601 constant_10, 602 constant_10, 603 0); 604 block->AddInstruction(new_array); 605 block->AddInstruction(new (allocator) HGoto()); 606 607 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 608 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 609 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 610 611 graph->AddBlock(loop_header); 612 graph->AddBlock(loop_body); 613 graph->AddBlock(exit); 614 block->AddSuccessor(loop_header); 615 loop_header->AddSuccessor(exit); // true successor 616 loop_header->AddSuccessor(loop_body); // false successor 617 loop_body->AddSuccessor(loop_header); 618 619 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 620 HInstruction* cmp = nullptr; 621 if (cond == kCondGE) { 622 cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10); 623 } else { 624 DCHECK(cond == kCondGT); 625 cmp = new (allocator) HGreaterThan(phi, constant_10); 626 } 627 HInstruction* if_inst = new (allocator) HIf(cmp); 628 loop_header->AddPhi(phi); 629 loop_header->AddInstruction(cmp); 630 loop_header->AddInstruction(if_inst); 631 phi->AddInput(constant_initial); 632 633 HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0); 634 HArrayLength* array_length = new (allocator) HArrayLength(null_check, 0); 635 HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); 636 HInstruction* array_set = new (allocator) HArraySet( 637 null_check, bounds_check, constant_10, Primitive::kPrimInt, 0); 638 HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); 639 loop_body->AddInstruction(null_check); 640 loop_body->AddInstruction(array_length); 641 loop_body->AddInstruction(bounds_check); 642 loop_body->AddInstruction(array_set); 643 loop_body->AddInstruction(add); 644 loop_body->AddInstruction(new (allocator) HGoto()); 645 phi->AddInput(add); 646 647 exit->AddInstruction(new (allocator) HExit()); 648 649 return bounds_check; 650 } 651 652 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3a) { 653 // int[] array = new int[10]; 654 // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. } 655 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGE); 656 RunBCE(); 657 ASSERT_TRUE(IsRemoved(bounds_check)); 658 } 659 660 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3b) { 661 // int[] array = new int[10]; 662 // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. } 663 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 1, kCondGE); 664 RunBCE(); 665 ASSERT_TRUE(IsRemoved(bounds_check)); 666 } 667 668 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3c) { 669 // int[] array = new int[10]; 670 // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. } 671 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGT); 672 RunBCE(); 673 ASSERT_FALSE(IsRemoved(bounds_check)); 674 } 675 676 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) { 677 // int[] array = new int[10]; 678 // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. } 679 HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 8, kCondGE); 680 RunBCE(); 681 ASSERT_TRUE(IsRemoved(bounds_check)); 682 } 683 684 // for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; } 685 static HInstruction* BuildSSAGraph4(HGraph* graph, 686 ArenaAllocator* allocator, 687 int initial, 688 IfCondition cond = kCondGE) { 689 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 690 graph->AddBlock(entry); 691 graph->SetEntryBlock(entry); 692 HInstruction* parameter = new (allocator) HParameterValue( 693 graph->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); 694 entry->AddInstruction(parameter); 695 696 HInstruction* constant_initial = graph->GetIntConstant(initial); 697 HInstruction* constant_1 = graph->GetIntConstant(1); 698 HInstruction* constant_10 = graph->GetIntConstant(10); 699 HInstruction* constant_minus_1 = graph->GetIntConstant(-1); 700 701 HBasicBlock* block = new (allocator) HBasicBlock(graph); 702 graph->AddBlock(block); 703 entry->AddSuccessor(block); 704 block->AddInstruction(new (allocator) HGoto()); 705 706 HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); 707 HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); 708 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 709 710 graph->AddBlock(loop_header); 711 graph->AddBlock(loop_body); 712 graph->AddBlock(exit); 713 block->AddSuccessor(loop_header); 714 loop_header->AddSuccessor(exit); // true successor 715 loop_header->AddSuccessor(loop_body); // false successor 716 loop_body->AddSuccessor(loop_header); 717 718 HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 719 HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); 720 HInstruction* array_length = new (allocator) HArrayLength(null_check, 0); 721 HInstruction* cmp = nullptr; 722 if (cond == kCondGE) { 723 cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); 724 } else if (cond == kCondGT) { 725 cmp = new (allocator) HGreaterThan(phi, array_length); 726 } 727 HInstruction* if_inst = new (allocator) HIf(cmp); 728 loop_header->AddPhi(phi); 729 loop_header->AddInstruction(null_check); 730 loop_header->AddInstruction(array_length); 731 loop_header->AddInstruction(cmp); 732 loop_header->AddInstruction(if_inst); 733 phi->AddInput(constant_initial); 734 735 null_check = new (allocator) HNullCheck(parameter, 0); 736 array_length = new (allocator) HArrayLength(null_check, 0); 737 HInstruction* sub = new (allocator) HSub(Primitive::kPrimInt, array_length, phi); 738 HInstruction* add_minus_1 = new (allocator) 739 HAdd(Primitive::kPrimInt, sub, constant_minus_1); 740 HInstruction* bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0); 741 HInstruction* array_set = new (allocator) HArraySet( 742 null_check, bounds_check, constant_10, Primitive::kPrimInt, 0); 743 HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_1); 744 loop_body->AddInstruction(null_check); 745 loop_body->AddInstruction(array_length); 746 loop_body->AddInstruction(sub); 747 loop_body->AddInstruction(add_minus_1); 748 loop_body->AddInstruction(bounds_check); 749 loop_body->AddInstruction(array_set); 750 loop_body->AddInstruction(add); 751 loop_body->AddInstruction(new (allocator) HGoto()); 752 phi->AddInput(add); 753 754 exit->AddInstruction(new (allocator) HExit()); 755 756 return bounds_check; 757 } 758 759 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4a) { 760 // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. } 761 HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0); 762 RunBCE(); 763 ASSERT_TRUE(IsRemoved(bounds_check)); 764 } 765 766 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4b) { 767 // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. } 768 HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 1); 769 RunBCE(); 770 ASSERT_TRUE(IsRemoved(bounds_check)); 771 } 772 773 TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) { 774 // for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. } 775 HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0, kCondGT); 776 RunBCE(); 777 ASSERT_FALSE(IsRemoved(bounds_check)); 778 } 779 780 // Bubble sort: 781 // (Every array access bounds-check can be eliminated.) 782 // for (int i=0; i<array.length-1; i++) { 783 // for (int j=0; j<array.length-i-1; j++) { 784 // if (array[j] > array[j+1]) { 785 // int temp = array[j+1]; 786 // array[j+1] = array[j]; 787 // array[j] = temp; 788 // } 789 // } 790 // } 791 TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) { 792 HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_); 793 graph_->AddBlock(entry); 794 graph_->SetEntryBlock(entry); 795 HInstruction* parameter = new (&allocator_) HParameterValue( 796 graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot); 797 entry->AddInstruction(parameter); 798 799 HInstruction* constant_0 = graph_->GetIntConstant(0); 800 HInstruction* constant_minus_1 = graph_->GetIntConstant(-1); 801 HInstruction* constant_1 = graph_->GetIntConstant(1); 802 803 HBasicBlock* block = new (&allocator_) HBasicBlock(graph_); 804 graph_->AddBlock(block); 805 entry->AddSuccessor(block); 806 block->AddInstruction(new (&allocator_) HGoto()); 807 808 HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_); 809 graph_->AddBlock(exit); 810 exit->AddInstruction(new (&allocator_) HExit()); 811 812 HBasicBlock* outer_header = new (&allocator_) HBasicBlock(graph_); 813 graph_->AddBlock(outer_header); 814 HPhi* phi_i = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt); 815 HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0); 816 HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0); 817 HAdd* add = new (&allocator_) HAdd(Primitive::kPrimInt, array_length, constant_minus_1); 818 HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(phi_i, add); 819 HIf* if_inst = new (&allocator_) HIf(cmp); 820 outer_header->AddPhi(phi_i); 821 outer_header->AddInstruction(null_check); 822 outer_header->AddInstruction(array_length); 823 outer_header->AddInstruction(add); 824 outer_header->AddInstruction(cmp); 825 outer_header->AddInstruction(if_inst); 826 phi_i->AddInput(constant_0); 827 828 HBasicBlock* inner_header = new (&allocator_) HBasicBlock(graph_); 829 graph_->AddBlock(inner_header); 830 HPhi* phi_j = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt); 831 null_check = new (&allocator_) HNullCheck(parameter, 0); 832 array_length = new (&allocator_) HArrayLength(null_check, 0); 833 HSub* sub = new (&allocator_) HSub(Primitive::kPrimInt, array_length, phi_i); 834 add = new (&allocator_) HAdd(Primitive::kPrimInt, sub, constant_minus_1); 835 cmp = new (&allocator_) HGreaterThanOrEqual(phi_j, add); 836 if_inst = new (&allocator_) HIf(cmp); 837 inner_header->AddPhi(phi_j); 838 inner_header->AddInstruction(null_check); 839 inner_header->AddInstruction(array_length); 840 inner_header->AddInstruction(sub); 841 inner_header->AddInstruction(add); 842 inner_header->AddInstruction(cmp); 843 inner_header->AddInstruction(if_inst); 844 phi_j->AddInput(constant_0); 845 846 HBasicBlock* inner_body_compare = new (&allocator_) HBasicBlock(graph_); 847 graph_->AddBlock(inner_body_compare); 848 null_check = new (&allocator_) HNullCheck(parameter, 0); 849 array_length = new (&allocator_) HArrayLength(null_check, 0); 850 HBoundsCheck* bounds_check1 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0); 851 HArrayGet* array_get_j = new (&allocator_) 852 HArrayGet(null_check, bounds_check1, Primitive::kPrimInt, 0); 853 inner_body_compare->AddInstruction(null_check); 854 inner_body_compare->AddInstruction(array_length); 855 inner_body_compare->AddInstruction(bounds_check1); 856 inner_body_compare->AddInstruction(array_get_j); 857 HInstruction* j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1); 858 null_check = new (&allocator_) HNullCheck(parameter, 0); 859 array_length = new (&allocator_) HArrayLength(null_check, 0); 860 HBoundsCheck* bounds_check2 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0); 861 HArrayGet* array_get_j_plus_1 = new (&allocator_) 862 HArrayGet(null_check, bounds_check2, Primitive::kPrimInt, 0); 863 cmp = new (&allocator_) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1); 864 if_inst = new (&allocator_) HIf(cmp); 865 inner_body_compare->AddInstruction(j_plus_1); 866 inner_body_compare->AddInstruction(null_check); 867 inner_body_compare->AddInstruction(array_length); 868 inner_body_compare->AddInstruction(bounds_check2); 869 inner_body_compare->AddInstruction(array_get_j_plus_1); 870 inner_body_compare->AddInstruction(cmp); 871 inner_body_compare->AddInstruction(if_inst); 872 873 HBasicBlock* inner_body_swap = new (&allocator_) HBasicBlock(graph_); 874 graph_->AddBlock(inner_body_swap); 875 j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1); 876 // temp = array[j+1] 877 null_check = new (&allocator_) HNullCheck(parameter, 0); 878 array_length = new (&allocator_) HArrayLength(null_check, 0); 879 HInstruction* bounds_check3 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0); 880 array_get_j_plus_1 = new (&allocator_) 881 HArrayGet(null_check, bounds_check3, Primitive::kPrimInt, 0); 882 inner_body_swap->AddInstruction(j_plus_1); 883 inner_body_swap->AddInstruction(null_check); 884 inner_body_swap->AddInstruction(array_length); 885 inner_body_swap->AddInstruction(bounds_check3); 886 inner_body_swap->AddInstruction(array_get_j_plus_1); 887 // array[j+1] = array[j] 888 null_check = new (&allocator_) HNullCheck(parameter, 0); 889 array_length = new (&allocator_) HArrayLength(null_check, 0); 890 HInstruction* bounds_check4 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0); 891 array_get_j = new (&allocator_) 892 HArrayGet(null_check, bounds_check4, Primitive::kPrimInt, 0); 893 inner_body_swap->AddInstruction(null_check); 894 inner_body_swap->AddInstruction(array_length); 895 inner_body_swap->AddInstruction(bounds_check4); 896 inner_body_swap->AddInstruction(array_get_j); 897 null_check = new (&allocator_) HNullCheck(parameter, 0); 898 array_length = new (&allocator_) HArrayLength(null_check, 0); 899 HInstruction* bounds_check5 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0); 900 HArraySet* array_set_j_plus_1 = new (&allocator_) 901 HArraySet(null_check, bounds_check5, array_get_j, Primitive::kPrimInt, 0); 902 inner_body_swap->AddInstruction(null_check); 903 inner_body_swap->AddInstruction(array_length); 904 inner_body_swap->AddInstruction(bounds_check5); 905 inner_body_swap->AddInstruction(array_set_j_plus_1); 906 // array[j] = temp 907 null_check = new (&allocator_) HNullCheck(parameter, 0); 908 array_length = new (&allocator_) HArrayLength(null_check, 0); 909 HInstruction* bounds_check6 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0); 910 HArraySet* array_set_j = new (&allocator_) 911 HArraySet(null_check, bounds_check6, array_get_j_plus_1, Primitive::kPrimInt, 0); 912 inner_body_swap->AddInstruction(null_check); 913 inner_body_swap->AddInstruction(array_length); 914 inner_body_swap->AddInstruction(bounds_check6); 915 inner_body_swap->AddInstruction(array_set_j); 916 inner_body_swap->AddInstruction(new (&allocator_) HGoto()); 917 918 HBasicBlock* inner_body_add = new (&allocator_) HBasicBlock(graph_); 919 graph_->AddBlock(inner_body_add); 920 add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1); 921 inner_body_add->AddInstruction(add); 922 inner_body_add->AddInstruction(new (&allocator_) HGoto()); 923 phi_j->AddInput(add); 924 925 HBasicBlock* outer_body_add = new (&allocator_) HBasicBlock(graph_); 926 graph_->AddBlock(outer_body_add); 927 add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_i, constant_1); 928 outer_body_add->AddInstruction(add); 929 outer_body_add->AddInstruction(new (&allocator_) HGoto()); 930 phi_i->AddInput(add); 931 932 block->AddSuccessor(outer_header); 933 outer_header->AddSuccessor(exit); 934 outer_header->AddSuccessor(inner_header); 935 inner_header->AddSuccessor(outer_body_add); 936 inner_header->AddSuccessor(inner_body_compare); 937 inner_body_compare->AddSuccessor(inner_body_add); 938 inner_body_compare->AddSuccessor(inner_body_swap); 939 inner_body_swap->AddSuccessor(inner_body_add); 940 inner_body_add->AddSuccessor(inner_header); 941 outer_body_add->AddSuccessor(outer_header); 942 943 RunBCE(); // gvn removes same bounds check already 944 945 ASSERT_TRUE(IsRemoved(bounds_check1)); 946 ASSERT_TRUE(IsRemoved(bounds_check2)); 947 ASSERT_TRUE(IsRemoved(bounds_check3)); 948 ASSERT_TRUE(IsRemoved(bounds_check4)); 949 ASSERT_TRUE(IsRemoved(bounds_check5)); 950 ASSERT_TRUE(IsRemoved(bounds_check6)); 951 } 952 953 } // namespace art 954
