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