src/Reactor/Optimizer.cpp

   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 <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::map<Ice::Operand*, Uses> uses;
  65                 std::map<Ice::Inst*, Ice::CfgNode*> node;
  66                 std::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 }