1 // Copyright 2016 The SwiftShader Authors. All Rights Reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #include "Optimizer.hpp" 16 17 #include "src/IceCfg.h" 18 #include "src/IceCfgNode.h" 19 20 #include <unordered_map> 21 #include <vector> 22 23 namespace 24 { 25 class Optimizer 26 { 27 public: 28 void run(Ice::Cfg *function); 29 30 private: 31 void analyzeUses(Ice::Cfg *function); 32 void eliminateDeadCode(); 33 void eliminateUnitializedLoads(); 34 void eliminateLoadsFollowingSingleStore(); 35 void optimizeStoresInSingleBasicBlock(); 36 37 void replace(Ice::Inst *instruction, Ice::Operand *newValue); 38 void deleteInstruction(Ice::Inst *instruction); 39 bool isDead(Ice::Inst *instruction); 40 41 static const Ice::InstIntrinsicCall *asLoadSubVector(const Ice::Inst *instruction); 42 static const Ice::InstIntrinsicCall *asStoreSubVector(const Ice::Inst *instruction); 43 static bool isLoad(const Ice::Inst &instruction); 44 static bool isStore(const Ice::Inst &instruction); 45 static Ice::Operand *storeAddress(const Ice::Inst *instruction); 46 static Ice::Operand *loadAddress(const Ice::Inst *instruction); 47 static Ice::Operand *storeData(const Ice::Inst *instruction); 48 static std::size_t storeSize(const Ice::Inst *instruction); 49 static bool loadTypeMatchesStore(const Ice::Inst *load, const Ice::Inst *store); 50 51 Ice::Cfg *function; 52 Ice::GlobalContext *context; 53 54 struct Uses : std::vector<Ice::Inst*> 55 { 56 bool areOnlyLoadStore() const; 57 void insert(Ice::Operand *value, Ice::Inst *instruction); 58 void erase(Ice::Inst *instruction); 59 60 std::vector<Ice::Inst*> loads; 61 std::vector<Ice::Inst*> stores; 62 }; 63 64 std::unordered_map<Ice::Operand*, Uses> uses; 65 std::unordered_map<Ice::Inst*, Ice::CfgNode*> node; 66 std::unordered_map<Ice::Variable*, Ice::Inst*> definition; 67 }; 68 69 void Optimizer::run(Ice::Cfg *function) 70 { 71 this->function = function; 72 this->context = function->getContext(); 73 74 analyzeUses(function); 75 76 eliminateDeadCode(); 77 eliminateUnitializedLoads(); 78 eliminateLoadsFollowingSingleStore(); 79 optimizeStoresInSingleBasicBlock(); 80 eliminateDeadCode(); 81 } 82 83 void Optimizer::eliminateDeadCode() 84 { 85 bool modified; 86 do 87 { 88 modified = false; 89 for(Ice::CfgNode *basicBlock : function->getNodes()) 90 { 91 for(Ice::Inst &inst : Ice::reverse_range(basicBlock->getInsts())) 92 { 93 if(inst.isDeleted()) 94 { 95 continue; 96 } 97 98 if(isDead(&inst)) 99 { 100 deleteInstruction(&inst); 101 modified = true; 102 } 103 } 104 } 105 } 106 while(modified); 107 } 108 109 void Optimizer::eliminateUnitializedLoads() 110 { 111 Ice::CfgNode *entryBlock = function->getEntryNode(); 112 113 for(Ice::Inst &alloca : entryBlock->getInsts()) 114 { 115 if(alloca.isDeleted()) 116 { 117 continue; 118 } 119 120 if(!llvm::isa<Ice::InstAlloca>(alloca)) 121 { 122 return; // Allocas are all at the top 123 } 124 125 Ice::Operand *address = alloca.getDest(); 126 const auto &addressEntry = uses.find(address); 127 const auto &addressUses = addressEntry->second; 128 129 if(!addressUses.areOnlyLoadStore()) 130 { 131 continue; 132 } 133 134 if(addressUses.stores.empty()) 135 { 136 for(Ice::Inst *load : addressUses.loads) 137 { 138 Ice::Variable *loadData = load->getDest(); 139 140 for(Ice::Inst *use : uses[loadData]) 141 { 142 for(Ice::SizeT i = 0; i < use->getSrcSize(); i++) 143 { 144 if(use->getSrc(i) == loadData) 145 { 146 auto *undef = context->getConstantUndef(loadData->getType()); 147 148 use->replaceSource(i, undef); 149 } 150 } 151 } 152 153 uses.erase(loadData); 154 155 load->setDeleted(); 156 } 157 158 alloca.setDeleted(); 159 uses.erase(addressEntry); 160 } 161 } 162 } 163 164 void Optimizer::eliminateLoadsFollowingSingleStore() 165 { 166 Ice::CfgNode *entryBlock = function->getEntryNode(); 167 168 for(Ice::Inst &alloca : entryBlock->getInsts()) 169 { 170 if(alloca.isDeleted()) 171 { 172 continue; 173 } 174 175 if(!llvm::isa<Ice::InstAlloca>(alloca)) 176 { 177 return; // Allocas are all at the top 178 } 179 180 Ice::Operand *address = alloca.getDest(); 181 const auto &addressEntry = uses.find(address); 182 auto &addressUses = addressEntry->second; 183 184 if(!addressUses.areOnlyLoadStore()) 185 { 186 continue; 187 } 188 189 if(addressUses.stores.size() == 1) 190 { 191 Ice::Inst *store = addressUses.stores[0]; 192 Ice::Operand *storeValue = storeData(store); 193 194 for(Ice::Inst *load = &*++store->getIterator(), *next = nullptr; load != next; next = load, load = &*++store->getIterator()) 195 { 196 if(load->isDeleted() || !isLoad(*load)) 197 { 198 continue; 199 } 200 201 if(loadAddress(load) != address) 202 { 203 continue; 204 } 205 206 if(!loadTypeMatchesStore(load, store)) 207 { 208 continue; 209 } 210 211 replace(load, storeValue); 212 213 for(size_t i = 0; i < addressUses.loads.size(); i++) 214 { 215 if(addressUses.loads[i] == load) 216 { 217 addressUses.loads[i] = addressUses.loads.back(); 218 addressUses.loads.pop_back(); 219 break; 220 } 221 } 222 223 for(size_t i = 0; i < addressUses.size(); i++) 224 { 225 if(addressUses[i] == load) 226 { 227 addressUses[i] = addressUses.back(); 228 addressUses.pop_back(); 229 break; 230 } 231 } 232 233 if(addressUses.size() == 1) 234 { 235 assert(addressUses[0] == store); 236 237 alloca.setDeleted(); 238 store->setDeleted(); 239 uses.erase(address); 240 241 auto &valueUses = uses[storeValue]; 242 243 for(size_t i = 0; i < valueUses.size(); i++) 244 { 245 if(valueUses[i] == store) 246 { 247 valueUses[i] = valueUses.back(); 248 valueUses.pop_back(); 249 break; 250 } 251 } 252 253 if(valueUses.empty()) 254 { 255 uses.erase(storeValue); 256 } 257 258 break; 259 } 260 } 261 } 262 } 263 } 264 265 void Optimizer::optimizeStoresInSingleBasicBlock() 266 { 267 Ice::CfgNode *entryBlock = function->getEntryNode(); 268 269 for(Ice::Inst &alloca : entryBlock->getInsts()) 270 { 271 if(alloca.isDeleted()) 272 { 273 continue; 274 } 275 276 if(!llvm::isa<Ice::InstAlloca>(alloca)) 277 { 278 return; // Allocas are all at the top 279 } 280 281 Ice::Operand *address = alloca.getDest(); 282 const auto &addressEntry = uses.find(address); 283 const auto &addressUses = addressEntry->second; 284 285 if(!addressUses.areOnlyLoadStore()) 286 { 287 continue; 288 } 289 290 Ice::CfgNode *singleBasicBlock = node[addressUses.stores[0]]; 291 292 for(size_t i = 1; i < addressUses.stores.size(); i++) 293 { 294 Ice::Inst *store = addressUses.stores[i]; 295 if(node[store] != singleBasicBlock) 296 { 297 singleBasicBlock = nullptr; 298 break; 299 } 300 } 301 302 if(singleBasicBlock) 303 { 304 auto &insts = singleBasicBlock->getInsts(); 305 Ice::Inst *store = nullptr; 306 Ice::Operand *storeValue = nullptr; 307 bool unmatchedLoads = false; 308 309 for(Ice::Inst &inst : insts) 310 { 311 if(inst.isDeleted()) 312 { 313 continue; 314 } 315 316 if(isStore(inst)) 317 { 318 if(storeAddress(&inst) != address) 319 { 320 continue; 321 } 322 323 // New store found. If we had a previous one, try to eliminate it. 324 if(store && !unmatchedLoads) 325 { 326 // If the previous store is wider than the new one, we can't eliminate it 327 // because there could be a wide load reading its non-overwritten data. 328 if(storeSize(&inst) >= storeSize(store)) 329 { 330 deleteInstruction(store); 331 } 332 } 333 334 store = &inst; 335 storeValue = storeData(store); 336 unmatchedLoads = false; 337 } 338 else if(isLoad(inst)) 339 { 340 Ice::Inst *load = &inst; 341 342 if(loadAddress(load) != address) 343 { 344 continue; 345 } 346 347 if(!loadTypeMatchesStore(load, store)) 348 { 349 unmatchedLoads = true; 350 continue; 351 } 352 353 replace(load, storeValue); 354 } 355 } 356 } 357 } 358 } 359 360 void Optimizer::analyzeUses(Ice::Cfg *function) 361 { 362 uses.clear(); 363 node.clear(); 364 definition.clear(); 365 366 for(Ice::CfgNode *basicBlock : function->getNodes()) 367 { 368 for(Ice::Inst &instruction : basicBlock->getInsts()) 369 { 370 if(instruction.isDeleted()) 371 { 372 continue; 373 } 374 375 node[&instruction] = basicBlock; 376 definition[instruction.getDest()] = &instruction; 377 378 for(Ice::SizeT i = 0; i < instruction.getSrcSize(); i++) 379 { 380 Ice::SizeT unique = 0; 381 for(; unique < i; unique++) 382 { 383 if(instruction.getSrc(i) == instruction.getSrc(unique)) 384 { 385 break; 386 } 387 } 388 389 if(i == unique) 390 { 391 Ice::Operand *src = instruction.getSrc(i); 392 uses[src].insert(src, &instruction); 393 } 394 } 395 } 396 } 397 } 398 399 void Optimizer::replace(Ice::Inst *instruction, Ice::Operand *newValue) 400 { 401 Ice::Variable *oldValue = instruction->getDest(); 402 403 if(!newValue) 404 { 405 newValue = context->getConstantUndef(oldValue->getType()); 406 } 407 408 for(Ice::Inst *use : uses[oldValue]) 409 { 410 assert(!use->isDeleted()); // Should have been removed from uses already 411 412 for(Ice::SizeT i = 0; i < use->getSrcSize(); i++) 413 { 414 if(use->getSrc(i) == oldValue) 415 { 416 use->replaceSource(i, newValue); 417 } 418 } 419 420 uses[newValue].insert(newValue, use); 421 } 422 423 uses.erase(oldValue); 424 425 deleteInstruction(instruction); 426 } 427 428 void Optimizer::deleteInstruction(Ice::Inst *instruction) 429 { 430 if(!instruction || instruction->isDeleted()) 431 { 432 return; 433 } 434 435 instruction->setDeleted(); 436 437 for(Ice::SizeT i = 0; i < instruction->getSrcSize(); i++) 438 { 439 Ice::Operand *src = instruction->getSrc(i); 440 441 const auto &srcEntry = uses.find(src); 442 443 if(srcEntry != uses.end()) 444 { 445 auto &srcUses = srcEntry->second; 446 447 srcUses.erase(instruction); 448 449 if(srcUses.empty()) 450 { 451 uses.erase(srcEntry); 452 453 if(Ice::Variable *var = llvm::dyn_cast<Ice::Variable>(src)) 454 { 455 deleteInstruction(definition[var]); 456 } 457 } 458 } 459 } 460 } 461 462 bool Optimizer::isDead(Ice::Inst *instruction) 463 { 464 Ice::Variable *dest = instruction->getDest(); 465 466 if(dest) 467 { 468 return uses[dest].empty() && !instruction->hasSideEffects(); 469 } 470 else if(isStore(*instruction)) 471 { 472 if(Ice::Variable *address = llvm::dyn_cast<Ice::Variable>(storeAddress(instruction))) 473 { 474 Ice::Inst *def = definition[address]; 475 476 if(def && llvm::isa<Ice::InstAlloca>(def)) 477 { 478 return uses[address].size() == uses[address].stores.size(); // Dead if all uses are stores 479 } 480 } 481 } 482 483 return false; 484 } 485 486 const Ice::InstIntrinsicCall *Optimizer::asLoadSubVector(const Ice::Inst *instruction) 487 { 488 if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction)) 489 { 490 if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::LoadSubVector) 491 { 492 return instrinsic; 493 } 494 } 495 496 return nullptr; 497 } 498 499 const Ice::InstIntrinsicCall *Optimizer::asStoreSubVector(const Ice::Inst *instruction) 500 { 501 if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction)) 502 { 503 if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::StoreSubVector) 504 { 505 return instrinsic; 506 } 507 } 508 509 return nullptr; 510 } 511 512 bool Optimizer::isLoad(const Ice::Inst &instruction) 513 { 514 if(llvm::isa<Ice::InstLoad>(&instruction)) 515 { 516 return true; 517 } 518 519 return asLoadSubVector(&instruction) != nullptr; 520 } 521 522 bool Optimizer::isStore(const Ice::Inst &instruction) 523 { 524 if(llvm::isa<Ice::InstStore>(&instruction)) 525 { 526 return true; 527 } 528 529 return asStoreSubVector(&instruction) != nullptr; 530 } 531 532 Ice::Operand *Optimizer::storeAddress(const Ice::Inst *instruction) 533 { 534 assert(isStore(*instruction)); 535 536 if(auto *store = llvm::dyn_cast<Ice::InstStore>(instruction)) 537 { 538 return store->getAddr(); 539 } 540 541 if(auto *storeSubVector = asStoreSubVector(instruction)) 542 { 543 return storeSubVector->getSrc(2); 544 } 545 546 return nullptr; 547 } 548 549 Ice::Operand *Optimizer::loadAddress(const Ice::Inst *instruction) 550 { 551 assert(isLoad(*instruction)); 552 553 if(auto *load = llvm::dyn_cast<Ice::InstLoad>(instruction)) 554 { 555 return load->getSourceAddress(); 556 } 557 558 if(auto *loadSubVector = asLoadSubVector(instruction)) 559 { 560 return loadSubVector->getSrc(1); 561 } 562 563 return nullptr; 564 } 565 566 Ice::Operand *Optimizer::storeData(const Ice::Inst *instruction) 567 { 568 assert(isStore(*instruction)); 569 570 if(auto *store = llvm::dyn_cast<Ice::InstStore>(instruction)) 571 { 572 return store->getData(); 573 } 574 575 if(auto *storeSubVector = asStoreSubVector(instruction)) 576 { 577 return storeSubVector->getSrc(1); 578 } 579 580 return nullptr; 581 } 582 583 std::size_t Optimizer::storeSize(const Ice::Inst *store) 584 { 585 assert(isStore(*store)); 586 587 if(auto *instStore = llvm::dyn_cast<Ice::InstStore>(store)) 588 { 589 return Ice::typeWidthInBytes(instStore->getData()->getType()); 590 } 591 592 if(auto *storeSubVector = asStoreSubVector(store)) 593 { 594 return llvm::cast<Ice::ConstantInteger32>(storeSubVector->getSrc(3))->getValue(); 595 } 596 597 return 0; 598 } 599 600 bool Optimizer::loadTypeMatchesStore(const Ice::Inst *load, const Ice::Inst *store) 601 { 602 if(!load || !store) 603 { 604 return false; 605 } 606 607 assert(isLoad(*load) && isStore(*store)); 608 assert(loadAddress(load) == storeAddress(store)); 609 610 if(auto *instStore = llvm::dyn_cast<Ice::InstStore>(store)) 611 { 612 if(auto *instLoad = llvm::dyn_cast<Ice::InstLoad>(load)) 613 { 614 return instStore->getData()->getType() == instLoad->getDest()->getType(); 615 } 616 } 617 618 if(auto *storeSubVector = asStoreSubVector(store)) 619 { 620 if(auto *loadSubVector = asLoadSubVector(load)) 621 { 622 // Check for matching type and sub-vector width. 623 return storeSubVector->getSrc(1)->getType() == loadSubVector->getDest()->getType() && 624 llvm::cast<Ice::ConstantInteger32>(storeSubVector->getSrc(3))->getValue() == 625 llvm::cast<Ice::ConstantInteger32>(loadSubVector->getSrc(2))->getValue(); 626 } 627 } 628 629 return false; 630 } 631 632 bool Optimizer::Uses::areOnlyLoadStore() const 633 { 634 return size() == (loads.size() + stores.size()); 635 } 636 637 void Optimizer::Uses::insert(Ice::Operand *value, Ice::Inst *instruction) 638 { 639 push_back(instruction); 640 641 if(isLoad(*instruction)) 642 { 643 if(value == loadAddress(instruction)) 644 { 645 loads.push_back(instruction); 646 } 647 } 648 else if(isStore(*instruction)) 649 { 650 if(value == storeAddress(instruction)) 651 { 652 stores.push_back(instruction); 653 } 654 } 655 } 656 657 void Optimizer::Uses::erase(Ice::Inst *instruction) 658 { 659 auto &uses = *this; 660 661 for(size_t i = 0; i < uses.size(); i++) 662 { 663 if(uses[i] == instruction) 664 { 665 uses[i] = back(); 666 pop_back(); 667 668 for(size_t i = 0; i < loads.size(); i++) 669 { 670 if(loads[i] == instruction) 671 { 672 loads[i] = loads.back(); 673 loads.pop_back(); 674 break; 675 } 676 } 677 678 for(size_t i = 0; i < stores.size(); i++) 679 { 680 if(stores[i] == instruction) 681 { 682 stores[i] = stores.back(); 683 stores.pop_back(); 684 break; 685 } 686 } 687 688 break; 689 } 690 } 691 } 692 } 693 694 namespace sw 695 { 696 void optimize(Ice::Cfg *function) 697 { 698 Optimizer optimizer; 699 700 optimizer.run(function); 701 } 702 }