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