Eliminate loads following a single store.

Bug swiftshader:27

Change-Id: I11238decf114381126a7465c462d918a3f16b0d8
Reviewed-on: https://swiftshader-review.googlesource.com/8273
Tested-by: Nicolas Capens <capn@google.com>
Reviewed-by: Alexis Hétu <sugoi@google.com>
Reviewed-by: Nicolas Capens <capn@google.com>

src/Reactor/Optimizer.cpp

diff --git a/src/Reactor/Optimizer.cpp b/src/Reactor/Optimizer.cpp
index 8ac70b1..a3b328e 100644
--- a/src/Reactor/Optimizer.cpp
+++ b/src/Reactor/Optimizer.cpp
@@ -31,11 +31,16 @@
 		void analyzeUses(Ice::Cfg *function);
 		void eliminateUnusedAllocas();
 		void eliminateUnitializedLoads();
+		void eliminateLoadsFollowingSingleStore();
+
+		void replace(Ice::Inst *instruction, Ice::Operand *newValue);
+		void deleteInstruction(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);
 
 		Ice::Cfg *function;
 		Ice::GlobalContext *context;
@@ -51,6 +56,8 @@
 		};
 
 		std::map<Ice::Operand*, Uses> uses;
+		std::map<Ice::Inst*, Ice::CfgNode*> node;
+		std::map<Ice::Variable*, Ice::Inst*> definition;
 	};
 
 	void Optimizer::run(Ice::Cfg *function)
@@ -62,6 +69,7 @@
 
 		eliminateUnusedAllocas();
 		eliminateUnitializedLoads();
+		eliminateLoadsFollowingSingleStore();
 	}
 
 	void Optimizer::eliminateUnusedAllocas()
@@ -139,9 +147,107 @@
 		}
 	}
 
+	void Optimizer::eliminateLoadsFollowingSingleStore()
+	{
+		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
+			}
+
+			Ice::Operand *address = alloca.getDest();
+			const auto &addressEntry = uses.find(address);
+			auto &addressUses = addressEntry->second;
+
+			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;
+					}
+
+					replace(load, storeValue);
+
+					for(int i = 0; i < addressUses.loads.size(); i++)
+					{
+						if(addressUses.loads[i] == load)
+						{
+							addressUses.loads[i] = addressUses.loads.back();
+							addressUses.loads.pop_back();
+							break;
+						}
+					}
+
+					for(int 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();
+						uses.erase(address);
+
+						auto &valueUses = uses[storeValue];
+
+						for(int i = 0; i < valueUses.size(); i++)
+						{
+							if(valueUses[i] == store)
+							{
+								valueUses[i] = valueUses.back();
+								valueUses.pop_back();
+								break;
+							}
+						}
+
+						if(valueUses.empty())
+						{
+							uses.erase(storeValue);
+						}
+
+						break;
+					}
+				}
+			}
+		}
+	}
+
 	void Optimizer::analyzeUses(Ice::Cfg *function)
 	{
 		uses.clear();
+		node.clear();
+		definition.clear();
 
 		for(Ice::CfgNode *basicBlock : function->getNodes())
 		{
@@ -152,6 +258,9 @@
 					continue;
 				}
 
+				node[&instruction] = basicBlock;
+				definition[instruction.getDest()] = &instruction;
+
 				for(int i = 0; i < instruction.getSrcSize(); i++)
 				{
 					int unique = 0;
@@ -173,6 +282,69 @@
 		}
 	}
 
+	void Optimizer::replace(Ice::Inst *instruction, Ice::Operand *newValue)
+	{
+		Ice::Variable *oldValue = instruction->getDest();
+
+		if(!newValue)
+		{
+			newValue = context->getConstantUndef(oldValue->getType());
+		}
+
+		for(Ice::Inst *use : uses[oldValue])
+		{
+			assert(!use->isDeleted());   // Should have been removed from uses already
+
+			for(int i = 0; i < use->getSrcSize(); i++)
+			{
+				if(use->getSrc(i) == oldValue)
+				{
+					use->replaceSource(i, newValue);
+				}
+			}
+
+			uses[newValue].insert(newValue, use);
+		}
+
+		uses.erase(oldValue);
+
+		deleteInstruction(instruction);
+	}
+
+	void Optimizer::deleteInstruction(Ice::Inst *instruction)
+	{
+		if(instruction->isDeleted())
+		{
+			return;
+		}
+
+		instruction->setDeleted();
+
+		for(int i = 0; i < instruction->getSrcSize(); i++)
+		{
+			Ice::Operand *src = instruction->getSrc(i);
+
+			const auto &srcEntry = uses.find(src);
+
+			if(srcEntry != uses.end())
+			{
+				auto &srcUses = srcEntry->second;
+
+				srcUses.erase(instruction);
+
+				if(srcUses.empty())
+				{
+					uses.erase(srcEntry);
+
+					if(Ice::Variable *var = llvm::dyn_cast<Ice::Variable>(src))
+					{
+						deleteInstruction(definition[var]);
+					}
+				}
+			}
+		}
+	}
+
 	bool Optimizer::isLoad(const Ice::Inst &instruction)
 	{
 		if(llvm::isa<Ice::InstLoad>(&instruction))
@@ -243,6 +415,26 @@
 		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 *instrinsic = llvm::dyn_cast<Ice::InstIntrinsicCall>(instruction))
+		{
+			if(instrinsic->getIntrinsicInfo().ID == Ice::Intrinsics::StoreSubVector)
+			{
+				return instrinsic->getSrc(1);
+			}
+		}
+
+		return nullptr;
+	}
+
 	bool Optimizer::Uses::areOnlyLoadStore() const
 	{
 		return size() == (loads.size() + stores.size());