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 eliminateUnusedAllocas();
  33                 void eliminateUnitializedLoads();
  34
  35                 static bool isLoad(const Ice::Inst &instruction);
  36                 static bool isStore(const Ice::Inst &instruction);
  37                 static Ice::Operand *storeAddress(const Ice::Inst *instruction);
  38                 static Ice::Operand *loadAddress(const Ice::Inst *instruction);
  39
  40                 Ice::Cfg *function;
  41                 Ice::GlobalContext *context;
  42
  43                 struct Uses : std::vector<Ice::Inst*>
  44                 {
  45                         bool areOnlyLoadStore() const;
  46                         void insert(Ice::Operand *value, Ice::Inst *instruction);
  47                         void erase(Ice::Inst *instruction);
  48
  49                         std::vector<Ice::Inst*> loads;
  50                         std::vector<Ice::Inst*> stores;
  51                 };
  52
  53                 std::map<Ice::Operand*, Uses> uses;
  54         };
  55
  56         void Optimizer::run(Ice::Cfg *function)
  57         {
  58                 this->function = function;
  59                 this->context = function->getContext();
  60
  61                 analyzeUses(function);
  62
  63                 eliminateUnusedAllocas();
  64                 eliminateUnitializedLoads();
  65         }
  66
  67         void Optimizer::eliminateUnusedAllocas()
  68         {
  69                 Ice::CfgNode *entryBlock = function->getEntryNode();
  70
  71                 for(Ice::Inst &alloca : entryBlock->getInsts())
  72                 {
  73                         if(!llvm::isa<Ice::InstAlloca>(alloca))
  74                         {
  75                                 return;   // Allocas are all at the top
  76                         }
  77
  78                         Ice::Operand *address = alloca.getDest();
  79
  80                         if(uses[address].empty())
  81                         {
  82                                 alloca.setDeleted();
  83                         }
  84                 }
  85         }
  86
  87         void Optimizer::eliminateUnitializedLoads()
  88         {
  89                 Ice::CfgNode *entryBlock = function->getEntryNode();
  90
  91                 for(Ice::Inst &alloca : entryBlock->getInsts())
  92                 {
  93                         if(alloca.isDeleted())
  94                         {
  95                                 continue;
  96                         }
  97
  98                         if(!llvm::isa<Ice::InstAlloca>(alloca))
  99                         {
 100                                 return;   // Allocas are all at the top
 101                         }
 102
 103                         Ice::Operand *address = alloca.getDest();
 104                         const auto &addressEntry = uses.find(address);
 105                         const auto &addressUses = addressEntry->second;
 106
 107                         if(!addressUses.areOnlyLoadStore())
 108                         {
 109                                 continue;
 110                         }
 111
 112                         if(addressUses.stores.empty())
 113                         {
 114                                 for(Ice::Inst *load : addressUses.loads)
 115                                 {
 116                                         Ice::Variable *loadData = load->getDest();
 117
 118                                         for(Ice::Inst *use : uses[loadData])
 119                                         {
 120                                                 for(int i = 0; i < use->getSrcSize(); i++)
 121                                                 {
 122                                                         if(use->getSrc(i) == loadData)
 123                                                         {
 124                                                                 auto *undef = context->getConstantUndef(loadData->getType());
 125
 126                                                                 use->replaceSource(i, undef);
 127                                                         }
 128                                                 }
 129                                         }
 130
 131                                         uses.erase(loadData);
 132
 133                                         load->setDeleted();
 134                                 }
 135
 136                                 alloca.setDeleted();
 137                                 uses.erase(addressEntry);
 138                         }
 139                 }
 140         }
 141
 142         void Optimizer::analyzeUses(Ice::Cfg *function)
 143         {
 144                 uses.clear();
 145
 146                 for(Ice::CfgNode *basicBlock : function->getNodes())
 147                 {
 148                         for(Ice::Inst &instruction : basicBlock->getInsts())
 149                         {
 150                                 if(instruction.isDeleted())
 151                                 {
 152                                         continue;
 153                                 }
 154
 155                                 for(int i = 0; i < instruction.getSrcSize(); i++)
 156                                 {
 157                                         int unique = 0;
 158                                         for(; unique < i; unique++)
 159                                         {
 160                                                 if(instruction.getSrc(i) == instruction.getSrc(unique))
 161                                                 {
 162                                                         break;
 163                                                 }
 164                                         }
 165
 166                                         if(i == unique)
 167                                         {
 168                                                 Ice::Operand *src = instruction.getSrc(i);
 169                                                 uses[src].insert(src, &instruction);
 170                                         }
 171                                 }
 172                         }
 173                 }
 174         }
 175
 176         bool Optimizer::isLoad(const Ice::Inst &instruction)
 177         {
 178                 if(llvm::isa<Ice::InstLoad>(&instruction))
 179                 {
 180                         return true;
 181                 }
 182
 183                 if(auto intrinsicCall = llvm::dyn_cast<Ice::InstIntrinsicCall>(&instruction))
 184                 {
 185                         return intrinsicCall->getIntrinsicInfo().ID == Ice::Intrinsics::LoadSubVector;
 186                 }
 187
 188                 return false;
 189         }
 190
 191         bool Optimizer::isStore(const Ice::Inst &instruction)
 192         {
 193                 if(llvm::isa<Ice::InstStore>(&instruction))
 194                 {
 195                         return true;
 196                 }
 197
 198                 if(auto intrinsicCall = llvm::dyn_cast<Ice::InstIntrinsicCall>(&instruction))
 199                 {
 200                         return intrinsicCall->getIntrinsicInfo().ID == Ice::Intrinsics::StoreSubVector;
 201                 }
 202
 203                 return false;
 204         }
 205
 206         Ice::Operand *Optimizer::storeAddress(const Ice::Inst *instruction)
 207         {
 208                 assert(isStore(*instruction));
 209
 210                 if(auto *store = llvm::dyn_cast<Ice::InstStore>(instruction))
 211                 {
 212                         return store->getAddr();
 213                 }
 214
 215                 if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction))
 216                 {
 217                         if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::StoreSubVector)
 218                         {
 219                                 return instrinsic->getSrc(2);
 220                         }
 221                 }
 222
 223                 return nullptr;
 224         }
 225
 226         Ice::Operand *Optimizer::loadAddress(const Ice::Inst *instruction)
 227         {
 228                 assert(isLoad(*instruction));
 229
 230                 if(auto *load = llvm::dyn_cast<Ice::InstLoad>(instruction))
 231                 {
 232                         return load->getSourceAddress();
 233                 }
 234
 235                 if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction))
 236                 {
 237                         if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::LoadSubVector)
 238                         {
 239                                 return instrinsic->getSrc(1);
 240                         }
 241                 }
 242
 243                 return nullptr;
 244         }
 245
 246         bool Optimizer::Uses::areOnlyLoadStore() const
 247         {
 248                 return size() == (loads.size() + stores.size());
 249         }
 250
 251         void Optimizer::Uses::insert(Ice::Operand *value, Ice::Inst *instruction)
 252         {
 253                 push_back(instruction);
 254
 255                 if(isLoad(*instruction))
 256                 {
 257                         if(value == loadAddress(instruction))
 258                         {
 259                                 loads.push_back(instruction);
 260                         }
 261                 }
 262                 else if(isStore(*instruction))
 263                 {
 264                         if(value == storeAddress(instruction))
 265                         {
 266                                 stores.push_back(instruction);
 267                         }
 268                 }
 269         }
 270
 271         void Optimizer::Uses::erase(Ice::Inst *instruction)
 272         {
 273                 auto &uses = *this;
 274
 275                 for(int i = 0; i < uses.size(); i++)
 276                 {
 277                         if(uses[i] == instruction)
 278                         {
 279                                 uses[i] = back();
 280                                 pop_back();
 281
 282                                 for(int i = 0; i < loads.size(); i++)
 283                                 {
 284                                         if(loads[i] == instruction)
 285                                         {
 286                                                 loads[i] = loads.back();
 287                                                 loads.pop_back();
 288                                                 break;
 289                                         }
 290                                 }
 291
 292                                 for(int i = 0; i < stores.size(); i++)
 293                                 {
 294                                         if(stores[i] == instruction)
 295                                         {
 296                                                 stores[i] = stores.back();
 297                                                 stores.pop_back();
 298                                                 break;
 299                                         }
 300                                 }
 301
 302                                 break;
 303                         }
 304                 }
 305         }
 306 }
 307
 308 namespace sw
 309 {
 310         void optimize(Ice::Cfg *function)
 311         {
 312                 Optimizer optimizer;
 313
 314                 optimizer.run(function);
 315         }
 316 }