#include "src/IceCfg.h"
#include "src/IceCfgNode.h"
-#include <map>
#include <vector>
namespace
private:
void analyzeUses(Ice::Cfg *function);
- void eliminateUnusedAllocas();
+ 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;
std::vector<Ice::Inst*> stores;
};
- std::map<Ice::Operand*, Uses> uses;
+ 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)
analyzeUses(function);
- eliminateUnusedAllocas();
+ 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::eliminateUnusedAllocas()
+ void Optimizer::eliminateUnitializedLoads()
{
Ice::CfgNode *entryBlock = function->getEntryNode();
for(Ice::Inst &alloca : entryBlock->getInsts())
{
+ if(alloca.isDeleted())
+ {
+ continue;
+ }
+
if(!llvm::isa<Ice::InstAlloca>(alloca))
{
- return; // Allocas are all at the top
+ break; // Allocas are all at the top
}
Ice::Operand *address = alloca.getDest();
- if(uses[address].empty())
+ 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::eliminateUnitializedLoads()
+ void Optimizer::eliminateLoadsFollowingSingleStore()
{
Ice::CfgNode *entryBlock = function->getEntryNode();
if(!llvm::isa<Ice::InstAlloca>(alloca))
{
- return; // Allocas are all at the top
+ break; // Allocas are all at the top
}
Ice::Operand *address = alloca.getDest();
- const auto &addressEntry = uses.find(address);
- const auto &addressUses = addressEntry->second;
+
+ if(!hasUses(address))
+ {
+ continue;
+ }
+
+ auto &addressUses = *getUses(address);
if(!addressUses.areOnlyLoadStore())
{
continue;
}
- if(addressUses.stores.empty())
+ if(addressUses.stores.size() == 1)
{
- for(Ice::Inst *load : addressUses.loads)
+ 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())
{
- Ice::Variable *loadData = load->getDest();
+ 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(Ice::Inst *use : uses[loadData])
+ for(size_t i = 0; i < addressUses.size(); i++)
{
- for(int i = 0; i < use->getSrcSize(); i++)
+ if(addressUses[i] == load)
{
- if(use->getSrc(i) == loadData)
+ 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++)
{
- auto *undef = context->getConstantUndef(loadData->getType());
+ if(valueUses[i] == store)
+ {
+ valueUses[i] = valueUses.back();
+ valueUses.pop_back();
+ break;
+ }
+ }
- use->replaceSource(i, undef);
+ if(valueUses.empty())
+ {
+ setUses(storeValue, nullptr);
}
}
+
+ break;
}
+ }
+ }
+ }
+ }
+
+ void Optimizer::optimizeStoresInSingleBasicBlock()
+ {
+ Ice::CfgNode *entryBlock = function->getEntryNode();
- uses.erase(loadData);
+ std::vector<std::vector<LoadStoreInst>* > allocatedVectors;
- load->setDeleted();
+ 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;
}
+ }
- alloca.setDeleted();
- uses.erase(addressEntry);
+ 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)
{
- uses.clear();
-
for(Ice::CfgNode *basicBlock : function->getNodes())
{
for(Ice::Inst &instruction : basicBlock->getInsts())
continue;
}
- for(int i = 0; i < instruction.getSrcSize(); i++)
+ setNode(&instruction, basicBlock);
+ if(instruction.getDest())
+ {
+ setDefinition(instruction.getDest(), &instruction);
+ }
+
+ for(Ice::SizeT i = 0; i < instruction.getSrcSize(); i++)
{
- int unique = 0;
+ Ice::SizeT unique = 0;
for(; unique < i; unique++)
{
if(instruction.getSrc(i) == instruction.getSrc(unique))
if(i == unique)
{
Ice::Operand *src = instruction.getSrc(i);
- uses[src].insert(src, &instruction);
+ getUses(src)->insert(src, &instruction);
}
}
}
}
}
- bool Optimizer::isLoad(const Ice::Inst &instruction)
+ void Optimizer::replace(Ice::Inst *instruction, Ice::Operand *newValue)
{
- if(llvm::isa<Ice::InstLoad>(&instruction))
+ Ice::Variable *oldValue = instruction->getDest();
+
+ if(!newValue)
{
- return true;
+ 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);
}
- if(auto intrinsicCall = llvm::dyn_cast<Ice::InstIntrinsicCall>(&instruction))
+ 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 intrinsicCall->getIntrinsicInfo().ID == Ice::Intrinsics::LoadSubVector;
+ 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;
}
- bool Optimizer::isStore(const Ice::Inst &instruction)
+ const Ice::InstIntrinsicCall *Optimizer::asLoadSubVector(const Ice::Inst *instruction)
{
- if(llvm::isa<Ice::InstStore>(&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;
}
- if(auto intrinsicCall = llvm::dyn_cast<Ice::InstIntrinsicCall>(&instruction))
+ return asLoadSubVector(&instruction) != nullptr;
+ }
+
+ bool Optimizer::isStore(const Ice::Inst &instruction)
+ {
+ if(llvm::isa<Ice::InstStore>(&instruction))
{
- return intrinsicCall->getIntrinsicInfo().ID == Ice::Intrinsics::StoreSubVector;
+ return true;
}
- return false;
+ return asStoreSubVector(&instruction) != nullptr;
}
Ice::Operand *Optimizer::storeAddress(const Ice::Inst *instruction)
return store->getAddr();
}
- if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction))
+ if(auto *storeSubVector = asStoreSubVector(instruction))
{
- if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::StoreSubVector)
- {
- return instrinsic->getSrc(2);
- }
+ return storeSubVector->getSrc(2);
}
return nullptr;
return load->getSourceAddress();
}
- if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction))
+ if(auto *loadSubVector = asLoadSubVector(instruction))
{
- if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::LoadSubVector)
+ 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 instrinsic->getSrc(1);
+ return instStore->getData()->getType() == instLoad->getDest()->getType();
}
}
- return nullptr;
+ 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
{
auto &uses = *this;
- for(int i = 0; i < uses.size(); i++)
+ for(size_t i = 0; i < uses.size(); i++)
{
if(uses[i] == instruction)
{
uses[i] = back();
pop_back();
- for(int i = 0; i < loads.size(); i++)
+ for(size_t i = 0; i < loads.size(); i++)
{
if(loads[i] == instruction)
{
}
}
- for(int i = 0; i < stores.size(); i++)
+ for(size_t i = 0; i < stores.size(); i++)
{
if(stores[i] == instruction)
{