blob: 8b74f829b37daf3d3effbe6ae0364bc5aa17b898 [file] [log] [blame]
// Copyright 2016 The SwiftShader Authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "Optimizer.hpp"
#include "src/IceCfg.h"
#include "src/IceCfgNode.h"
#include <vector>
namespace {
class Optimizer
{
public:
void run(Ice::Cfg *function);
private:
void analyzeUses(Ice::Cfg *function);
void eliminateDeadCode();
void eliminateUnitializedLoads();
void eliminateLoadsFollowingSingleStore();
void optimizeStoresInSingleBasicBlock();
void replace(Ice::Inst *instruction, Ice::Operand *newValue);
void deleteInstruction(Ice::Inst *instruction);
bool isDead(Ice::Inst *instruction);
static const Ice::InstIntrinsicCall *asLoadSubVector(const Ice::Inst *instruction);
static const Ice::InstIntrinsicCall *asStoreSubVector(const Ice::Inst *instruction);
static bool isLoad(const Ice::Inst &instruction);
static bool isStore(const Ice::Inst &instruction);
static Ice::Operand *storeAddress(const Ice::Inst *instruction);
static Ice::Operand *loadAddress(const Ice::Inst *instruction);
static Ice::Operand *storeData(const Ice::Inst *instruction);
static std::size_t storeSize(const Ice::Inst *instruction);
static bool loadTypeMatchesStore(const Ice::Inst *load, const Ice::Inst *store);
Ice::Cfg *function;
Ice::GlobalContext *context;
struct Uses : std::vector<Ice::Inst*>
{
bool areOnlyLoadStore() const;
void insert(Ice::Operand *value, Ice::Inst *instruction);
void erase(Ice::Inst *instruction);
std::vector<Ice::Inst*> loads;
std::vector<Ice::Inst*> stores;
};
struct LoadStoreInst
{
LoadStoreInst(Ice::Inst* inst, bool isStore)
: inst(inst),
address(isStore ? storeAddress(inst) : loadAddress(inst)),
isStore(isStore)
{
}
Ice::Inst* inst;
Ice::Operand *address;
bool isStore;
};
Optimizer::Uses* getUses(Ice::Operand*);
void setUses(Ice::Operand*, Optimizer::Uses*);
bool hasUses(Ice::Operand*) const;
Ice::CfgNode* getNode(Ice::Inst*);
void setNode(Ice::Inst*, Ice::CfgNode*);
Ice::Inst* getDefinition(Ice::Variable*);
void setDefinition(Ice::Variable*, Ice::Inst*);
const std::vector<LoadStoreInst>& getLoadStoreInsts(Ice::CfgNode*);
void setLoadStoreInsts(Ice::CfgNode*, std::vector<LoadStoreInst>*);
bool hasLoadStoreInsts(Ice::CfgNode* node) const;
std::vector<Optimizer::Uses*> allocatedUses;
};
void Optimizer::run(Ice::Cfg *function)
{
this->function = function;
this->context = function->getContext();
analyzeUses(function);
eliminateDeadCode();
eliminateUnitializedLoads();
eliminateLoadsFollowingSingleStore();
optimizeStoresInSingleBasicBlock();
eliminateDeadCode();
for(auto uses : allocatedUses)
{
delete uses;
}
allocatedUses.clear();
}
void Optimizer::eliminateDeadCode()
{
bool modified;
do
{
modified = false;
for(Ice::CfgNode *basicBlock : function->getNodes())
{
for(Ice::Inst &inst : Ice::reverse_range(basicBlock->getInsts()))
{
if(inst.isDeleted())
{
continue;
}
if(isDead(&inst))
{
deleteInstruction(&inst);
modified = true;
}
}
}
}
while(modified);
}
void Optimizer::eliminateUnitializedLoads()
{
Ice::CfgNode *entryBlock = function->getEntryNode();
for(Ice::Inst &alloca : entryBlock->getInsts())
{
if(alloca.isDeleted())
{
continue;
}
if(!llvm::isa<Ice::InstAlloca>(alloca))
{
break; // Allocas are all at the top
}
Ice::Operand *address = alloca.getDest();
if(!hasUses(address))
{
continue;
}
const auto &addressUses = *getUses(address);
if(!addressUses.areOnlyLoadStore())
{
continue;
}
if(addressUses.stores.empty())
{
for(Ice::Inst *load : addressUses.loads)
{
Ice::Variable *loadData = load->getDest();
if(hasUses(loadData))
{
for(Ice::Inst *use : *getUses(loadData))
{
for(Ice::SizeT i = 0; i < use->getSrcSize(); i++)
{
if(use->getSrc(i) == loadData)
{
auto *undef = context->getConstantUndef(loadData->getType());
use->replaceSource(i, undef);
}
}
}
setUses(loadData, nullptr);
}
load->setDeleted();
}
alloca.setDeleted();
setUses(address, nullptr);
}
}
}
void Optimizer::eliminateLoadsFollowingSingleStore()
{
Ice::CfgNode *entryBlock = function->getEntryNode();
for(Ice::Inst &alloca : entryBlock->getInsts())
{
if(alloca.isDeleted())
{
continue;
}
if(!llvm::isa<Ice::InstAlloca>(alloca))
{
break; // Allocas are all at the top
}
Ice::Operand *address = alloca.getDest();
if(!hasUses(address))
{
continue;
}
auto &addressUses = *getUses(address);
if(!addressUses.areOnlyLoadStore())
{
continue;
}
if(addressUses.stores.size() == 1)
{
Ice::Inst *store = addressUses.stores[0];
Ice::Operand *storeValue = storeData(store);
for(Ice::Inst *load = &*++store->getIterator(), *next = nullptr; load != next; next = load, load = &*++store->getIterator())
{
if(load->isDeleted() || !isLoad(*load))
{
continue;
}
if(loadAddress(load) != address)
{
continue;
}
if(!loadTypeMatchesStore(load, store))
{
continue;
}
replace(load, storeValue);
for(size_t i = 0; i < addressUses.loads.size(); i++)
{
if(addressUses.loads[i] == load)
{
addressUses.loads[i] = addressUses.loads.back();
addressUses.loads.pop_back();
break;
}
}
for(size_t i = 0; i < addressUses.size(); i++)
{
if(addressUses[i] == load)
{
addressUses[i] = addressUses.back();
addressUses.pop_back();
break;
}
}
if(addressUses.size() == 1)
{
assert(addressUses[0] == store);
alloca.setDeleted();
store->setDeleted();
setUses(address, nullptr);
if(hasUses(storeValue))
{
auto &valueUses = *getUses(storeValue);
for(size_t i = 0; i < valueUses.size(); i++)
{
if(valueUses[i] == store)
{
valueUses[i] = valueUses.back();
valueUses.pop_back();
break;
}
}
if(valueUses.empty())
{
setUses(storeValue, nullptr);
}
}
break;
}
}
}
}
}
void Optimizer::optimizeStoresInSingleBasicBlock()
{
Ice::CfgNode *entryBlock = function->getEntryNode();
std::vector<std::vector<LoadStoreInst>* > allocatedVectors;
for(Ice::Inst &alloca : entryBlock->getInsts())
{
if(alloca.isDeleted())
{
continue;
}
if(!llvm::isa<Ice::InstAlloca>(alloca))
{
break; // Allocas are all at the top
}
Ice::Operand *address = alloca.getDest();
if(!hasUses(address))
{
continue;
}
const auto &addressUses = *getUses(address);
if(!addressUses.areOnlyLoadStore())
{
continue;
}
Ice::CfgNode *singleBasicBlock = getNode(addressUses.stores[0]);
for(size_t i = 1; i < addressUses.stores.size(); i++)
{
Ice::Inst *store = addressUses.stores[i];
if(getNode(store) != singleBasicBlock)
{
singleBasicBlock = nullptr;
break;
}
}
if(singleBasicBlock)
{
if(!hasLoadStoreInsts(singleBasicBlock))
{
std::vector<LoadStoreInst>* loadStoreInstVector = new std::vector<LoadStoreInst>();
setLoadStoreInsts(singleBasicBlock, loadStoreInstVector);
allocatedVectors.push_back(loadStoreInstVector);
for(Ice::Inst &inst : singleBasicBlock->getInsts())
{
if(inst.isDeleted())
{
continue;
}
bool isStoreInst = isStore(inst);
bool isLoadInst = isLoad(inst);
if(isStoreInst || isLoadInst)
{
loadStoreInstVector->push_back(LoadStoreInst(&inst, isStoreInst));
}
}
}
Ice::Inst *store = nullptr;
Ice::Operand *storeValue = nullptr;
bool unmatchedLoads = false;
for(auto& loadStoreInst : getLoadStoreInsts(singleBasicBlock))
{
Ice::Inst* inst = loadStoreInst.inst;
if((loadStoreInst.address != address) || inst->isDeleted())
{
continue;
}
if(loadStoreInst.isStore)
{
// New store found. If we had a previous one, try to eliminate it.
if(store && !unmatchedLoads)
{
// If the previous store is wider than the new one, we can't eliminate it
// because there could be a wide load reading its non-overwritten data.
if(storeSize(inst) >= storeSize(store))
{
deleteInstruction(store);
}
}
store = inst;
storeValue = storeData(store);
unmatchedLoads = false;
}
else
{
if(!loadTypeMatchesStore(inst, store))
{
unmatchedLoads = true;
continue;
}
replace(inst, storeValue);
}
}
}
}
for(auto loadStoreInstVector : allocatedVectors)
{
delete loadStoreInstVector;
}
}
void Optimizer::analyzeUses(Ice::Cfg *function)
{
for(Ice::CfgNode *basicBlock : function->getNodes())
{
for(Ice::Inst &instruction : basicBlock->getInsts())
{
if(instruction.isDeleted())
{
continue;
}
setNode(&instruction, basicBlock);
if(instruction.getDest())
{
setDefinition(instruction.getDest(), &instruction);
}
for(Ice::SizeT i = 0; i < instruction.getSrcSize(); i++)
{
Ice::SizeT unique = 0;
for(; unique < i; unique++)
{
if(instruction.getSrc(i) == instruction.getSrc(unique))
{
break;
}
}
if(i == unique)
{
Ice::Operand *src = instruction.getSrc(i);
getUses(src)->insert(src, &instruction);
}
}
}
}
}
void Optimizer::replace(Ice::Inst *instruction, Ice::Operand *newValue)
{
Ice::Variable *oldValue = instruction->getDest();
if(!newValue)
{
newValue = context->getConstantUndef(oldValue->getType());
}
if(hasUses(oldValue))
{
for(Ice::Inst *use : *getUses(oldValue))
{
assert(!use->isDeleted()); // Should have been removed from uses already
for(Ice::SizeT i = 0; i < use->getSrcSize(); i++)
{
if(use->getSrc(i) == oldValue)
{
use->replaceSource(i, newValue);
}
}
getUses(newValue)->insert(newValue, use);
}
setUses(oldValue, nullptr);
}
deleteInstruction(instruction);
}
void Optimizer::deleteInstruction(Ice::Inst *instruction)
{
if(!instruction || instruction->isDeleted())
{
return;
}
instruction->setDeleted();
for(Ice::SizeT i = 0; i < instruction->getSrcSize(); i++)
{
Ice::Operand *src = instruction->getSrc(i);
if(hasUses(src))
{
auto &srcUses = *getUses(src);
srcUses.erase(instruction);
if(srcUses.empty())
{
setUses(src, nullptr);
if(Ice::Variable *var = llvm::dyn_cast<Ice::Variable>(src))
{
deleteInstruction(getDefinition(var));
}
}
}
}
}
bool Optimizer::isDead(Ice::Inst *instruction)
{
Ice::Variable *dest = instruction->getDest();
if(dest)
{
return (!hasUses(dest) || getUses(dest)->empty()) && !instruction->hasSideEffects();
}
else if(isStore(*instruction))
{
if(Ice::Variable *address = llvm::dyn_cast<Ice::Variable>(storeAddress(instruction)))
{
Ice::Inst *def = getDefinition(address);
if(def && llvm::isa<Ice::InstAlloca>(def))
{
if(hasUses(address))
{
Optimizer::Uses* uses = getUses(address);
return uses->size() == uses->stores.size(); // Dead if all uses are stores
}
else
{
return true; // No uses
}
}
}
}
return false;
}
const Ice::InstIntrinsicCall *Optimizer::asLoadSubVector(const Ice::Inst *instruction)
{
if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction))
{
if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::LoadSubVector)
{
return instrinsic;
}
}
return nullptr;
}
const Ice::InstIntrinsicCall *Optimizer::asStoreSubVector(const Ice::Inst *instruction)
{
if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction))
{
if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::StoreSubVector)
{
return instrinsic;
}
}
return nullptr;
}
bool Optimizer::isLoad(const Ice::Inst &instruction)
{
if(llvm::isa<Ice::InstLoad>(&instruction))
{
return true;
}
return asLoadSubVector(&instruction) != nullptr;
}
bool Optimizer::isStore(const Ice::Inst &instruction)
{
if(llvm::isa<Ice::InstStore>(&instruction))
{
return true;
}
return asStoreSubVector(&instruction) != nullptr;
}
Ice::Operand *Optimizer::storeAddress(const Ice::Inst *instruction)
{
assert(isStore(*instruction));
if(auto *store = llvm::dyn_cast<Ice::InstStore>(instruction))
{
return store->getAddr();
}
if(auto *storeSubVector = asStoreSubVector(instruction))
{
return storeSubVector->getSrc(2);
}
return nullptr;
}
Ice::Operand *Optimizer::loadAddress(const Ice::Inst *instruction)
{
assert(isLoad(*instruction));
if(auto *load = llvm::dyn_cast<Ice::InstLoad>(instruction))
{
return load->getSourceAddress();
}
if(auto *loadSubVector = asLoadSubVector(instruction))
{
return loadSubVector->getSrc(1);
}
return nullptr;
}
Ice::Operand *Optimizer::storeData(const Ice::Inst *instruction)
{
assert(isStore(*instruction));
if(auto *store = llvm::dyn_cast<Ice::InstStore>(instruction))
{
return store->getData();
}
if(auto *storeSubVector = asStoreSubVector(instruction))
{
return storeSubVector->getSrc(1);
}
return nullptr;
}
std::size_t Optimizer::storeSize(const Ice::Inst *store)
{
assert(isStore(*store));
if(auto *instStore = llvm::dyn_cast<Ice::InstStore>(store))
{
return Ice::typeWidthInBytes(instStore->getData()->getType());
}
if(auto *storeSubVector = asStoreSubVector(store))
{
return llvm::cast<Ice::ConstantInteger32>(storeSubVector->getSrc(3))->getValue();
}
return 0;
}
bool Optimizer::loadTypeMatchesStore(const Ice::Inst *load, const Ice::Inst *store)
{
if(!load || !store)
{
return false;
}
assert(isLoad(*load) && isStore(*store));
assert(loadAddress(load) == storeAddress(store));
if(auto *instStore = llvm::dyn_cast<Ice::InstStore>(store))
{
if(auto *instLoad = llvm::dyn_cast<Ice::InstLoad>(load))
{
return instStore->getData()->getType() == instLoad->getDest()->getType();
}
}
if(auto *storeSubVector = asStoreSubVector(store))
{
if(auto *loadSubVector = asLoadSubVector(load))
{
// Check for matching type and sub-vector width.
return storeSubVector->getSrc(1)->getType() == loadSubVector->getDest()->getType() &&
llvm::cast<Ice::ConstantInteger32>(storeSubVector->getSrc(3))->getValue() ==
llvm::cast<Ice::ConstantInteger32>(loadSubVector->getSrc(2))->getValue();
}
}
return false;
}
Optimizer::Uses* Optimizer::getUses(Ice::Operand* operand)
{
Optimizer::Uses* uses = (Optimizer::Uses*)operand->Ice::Operand::getExternalData();
if(!uses)
{
uses = new Optimizer::Uses;
setUses(operand, uses);
allocatedUses.push_back(uses);
}
return uses;
}
void Optimizer::setUses(Ice::Operand* operand, Optimizer::Uses* uses)
{
operand->Ice::Operand::setExternalData(uses);
}
bool Optimizer::hasUses(Ice::Operand* operand) const
{
return operand->Ice::Operand::getExternalData() != nullptr;
}
Ice::CfgNode* Optimizer::getNode(Ice::Inst* inst)
{
return (Ice::CfgNode*)inst->Ice::Inst::getExternalData();
}
void Optimizer::setNode(Ice::Inst* inst, Ice::CfgNode* node)
{
inst->Ice::Inst::setExternalData(node);
}
Ice::Inst* Optimizer::getDefinition(Ice::Variable* var)
{
return (Ice::Inst*)var->Ice::Variable::getExternalData();
}
void Optimizer::setDefinition(Ice::Variable* var, Ice::Inst* inst)
{
var->Ice::Variable::setExternalData(inst);
}
const std::vector<Optimizer::LoadStoreInst>& Optimizer::getLoadStoreInsts(Ice::CfgNode* node)
{
return *((const std::vector<LoadStoreInst>*)node->Ice::CfgNode::getExternalData());
}
void Optimizer::setLoadStoreInsts(Ice::CfgNode* node, std::vector<LoadStoreInst>* insts)
{
node->Ice::CfgNode::setExternalData(insts);
}
bool Optimizer::hasLoadStoreInsts(Ice::CfgNode* node) const
{
return node->Ice::CfgNode::getExternalData() != nullptr;
}
bool Optimizer::Uses::areOnlyLoadStore() const
{
return size() == (loads.size() + stores.size());
}
void Optimizer::Uses::insert(Ice::Operand *value, Ice::Inst *instruction)
{
push_back(instruction);
if(isLoad(*instruction))
{
if(value == loadAddress(instruction))
{
loads.push_back(instruction);
}
}
else if(isStore(*instruction))
{
if(value == storeAddress(instruction))
{
stores.push_back(instruction);
}
}
}
void Optimizer::Uses::erase(Ice::Inst *instruction)
{
auto &uses = *this;
for(size_t i = 0; i < uses.size(); i++)
{
if(uses[i] == instruction)
{
uses[i] = back();
pop_back();
for(size_t i = 0; i < loads.size(); i++)
{
if(loads[i] == instruction)
{
loads[i] = loads.back();
loads.pop_back();
break;
}
}
for(size_t i = 0; i < stores.size(); i++)
{
if(stores[i] == instruction)
{
stores[i] = stores.back();
stores.pop_back();
break;
}
}
break;
}
}
}
} // anonymous namespace
namespace rr {
void optimize(Ice::Cfg *function)
{
Optimizer optimizer;
optimizer.run(function);
}
} // namespace rr