src/Reactor/Optimizer.cpp

// 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 <unordered_map>
#include <vector>

namespace {

class Optimizer
{
public:
	Optimizer(rr::Nucleus::OptimizerReport *report)
	    : report(report)
	{
	}

	void run(Ice::Cfg *function);

private:
	void analyzeUses(Ice::Cfg *function);

	void eliminateDeadCode();
	void eliminateUnitializedLoads();
	void propagateAlloca();
	void performScalarReplacementOfAggregates();
	void optimizeSingleBasicBlockLoadsStores();

	void replace(Ice::Inst *instruction, Ice::Operand *newValue);
	void deleteInstruction(Ice::Inst *instruction);
	bool isDead(Ice::Inst *instruction);
	bool isStaticallyIndexedArray(Ice::Operand *allocaAddress);
	Ice::InstAlloca *allocaOf(Ice::Operand *address);

	static const Ice::InstIntrinsic *asLoadSubVector(const Ice::Inst *instruction);
	static const Ice::InstIntrinsic *asStoreSubVector(const Ice::Inst *instruction);
	static bool isLoad(const Ice::Inst &instruction);
	static bool isStore(const Ice::Inst &instruction);
	static bool loadTypeMatchesStore(const Ice::Inst *load, const Ice::Inst *store);
	static bool storeTypeMatchesStore(const Ice::Inst *store1, const Ice::Inst *store2);

	void collectDiagnostics();

	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 ? inst->getStoreAddress() : inst->getLoadAddress())
		    , 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::Inst *getDefinition(Ice::Variable *);
	void setDefinition(Ice::Variable *, Ice::Inst *);

	std::vector<Ice::Operand *> operandsWithUses;

	rr::Nucleus::OptimizerReport *report = nullptr;
};

void Optimizer::run(Ice::Cfg *function)
{
	this->function = function;
	this->context = function->getContext();

	analyzeUses(function);

	// Start by eliminating any dead code, to avoid redundant work for the
	// subsequent optimization passes.
	eliminateDeadCode();
	eliminateUnitializedLoads();

	// Eliminate allocas which store the address of other allocas.
	propagateAlloca();

	// Replace arrays with individual elements if only statically indexed.
	performScalarReplacementOfAggregates();

	// Iterate through basic blocks to propagate loads following stores.
	optimizeSingleBasicBlockLoadsStores();

	for(auto operand : operandsWithUses)
	{
		// Deletes the Uses instance on the operand
		setUses(operand, nullptr);
	}
	operandsWithUses.clear();

	collectDiagnostics();
}

// Eliminates allocas which store the address of other allocas.
void Optimizer::propagateAlloca()
{
	Ice::CfgNode *entryBlock = function->getEntryNode();
	Ice::InstList &instList = entryBlock->getInsts();

	for(Ice::Inst &inst : instList)
	{
		if(inst.isDeleted())
		{
			continue;
		}

		auto *alloca = llvm::dyn_cast<Ice::InstAlloca>(&inst);

		if(!alloca)
		{
			break;  // Allocas are all at the top
		}

		// Look for stores of this alloca's address.
		Ice::Operand *address = alloca->getDest();
		Uses uses = *getUses(address);  // Hard copy

		for(auto *store : uses)
		{
			if(isStore(*store) && store->getData() == address)
			{
				Ice::Operand *dest = store->getStoreAddress();
				Ice::Variable *destVar = llvm::dyn_cast<Ice::Variable>(dest);
				Ice::Inst *def = destVar ? getDefinition(destVar) : nullptr;

				// If the address is stored into another stack variable, eliminate the latter.
				if(def && def->getKind() == Ice::Inst::Alloca)
				{
					Uses destUses = *getUses(dest);  // Hard copy

					// Make sure the only store into the stack variable is this address, and that all of its other uses are loads.
					// This prevents dynamic array loads/stores to be replaced by a scalar.
					if((destUses.stores.size() == 1) && (destUses.loads.size() == destUses.size() - 1))
					{
						for(auto *load : destUses.loads)
						{
							replace(load, address);
						}

						// The address is now only stored, never loaded, so the store can be eliminated, together with its alloca.
						assert(getUses(dest)->size() == 1);
						deleteInstruction(store);
						assert(def->isDeleted());
					}
				}
			}
		}
	}
}

Ice::Type pointerType()
{
	if(sizeof(void *) == 8)
	{
		return Ice::IceType_i64;
	}
	else
	{
		return Ice::IceType_i32;
	}
}

// Replace arrays with individual elements if only statically indexed.
void Optimizer::performScalarReplacementOfAggregates()
{
	std::vector<Ice::InstAlloca *> newAllocas;

	Ice::CfgNode *entryBlock = function->getEntryNode();
	Ice::InstList &instList = entryBlock->getInsts();

	for(Ice::Inst &inst : instList)
	{
		if(inst.isDeleted())
		{
			continue;
		}

		auto *alloca = llvm::dyn_cast<Ice::InstAlloca>(&inst);

		if(!alloca)
		{
			break;  // Allocas are all at the top
		}

		uint32_t sizeInBytes = llvm::cast<Ice::ConstantInteger32>(alloca->getSizeInBytes())->getValue();
		uint32_t alignInBytes = alloca->getAlignInBytes();

		// This pass relies on array elements to be naturally aligned (i.e. matches the type size).
		assert(sizeInBytes >= alignInBytes);
		assert(sizeInBytes % alignInBytes == 0);
		uint32_t elementCount = sizeInBytes / alignInBytes;

		Ice::Operand *address = alloca->getDest();

		if(isStaticallyIndexedArray(address))
		{
			// Delete the old array.
			alloca->setDeleted();

			// Allocate new stack slots for each element.
			std::vector<Ice::Variable *> newAddress(elementCount);
			auto *bytes = Ice::ConstantInteger32::create(context, Ice::IceType_i32, alignInBytes);

			for(uint32_t i = 0; i < elementCount; i++)
			{
				newAddress[i] = function->makeVariable(pointerType());
				auto *alloca = Ice::InstAlloca::create(function, newAddress[i], bytes, alignInBytes);
				setDefinition(newAddress[i], alloca);

				newAllocas.push_back(alloca);
			}

			Uses uses = *getUses(address);  // Hard copy

			for(auto *use : uses)
			{
				assert(!use->isDeleted());

				if(isLoad(*use))  // Direct use of base address
				{
					use->replaceSource(asLoadSubVector(use) ? 1 : 0, newAddress[0]);
					getUses(newAddress[0])->insert(newAddress[0], use);
				}
				else if(isStore(*use))  // Direct use of base address
				{
					use->replaceSource(asStoreSubVector(use) ? 2 : 1, newAddress[0]);
					getUses(newAddress[0])->insert(newAddress[0], use);
				}
				else  // Statically indexed use
				{
					auto *arithmetic = llvm::cast<Ice::InstArithmetic>(use);

					if(arithmetic->getOp() == Ice::InstArithmetic::Add)
					{
						auto *rhs = arithmetic->getSrc(1);
						int32_t offset = llvm::cast<Ice::ConstantInteger32>(rhs)->getValue();

						assert(offset % alignInBytes == 0);
						int32_t index = offset / alignInBytes;
						assert(static_cast<uint32_t>(index) < elementCount);

						replace(arithmetic, newAddress[index]);
					}
					else
						assert(false && "Mismatch between isStaticallyIndexedArray() and scalarReplacementOfAggregates()");
				}
			}
		}
	}

	// After looping over all the old allocas, add any new ones that replace them.
	// They're added to the front in reverse order, to retain their original order.
	for(size_t i = newAllocas.size(); i-- != 0;)
	{
		if(!isDead(newAllocas[i]))
		{
			instList.push_front(newAllocas[i]);
		}
	}
}

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);
		}
	}
}

// Iterate through basic blocks to propagate stores to subsequent loads.
void Optimizer::optimizeSingleBasicBlockLoadsStores()
{
	for(Ice::CfgNode *block : function->getNodes())
	{
		// For each stack variable keep track of the last store instruction.
		// To eliminate a store followed by another store to the same alloca address
		// we must also know whether all loads have been replaced by the store value.
		struct LastStore
		{
			Ice::Inst *store;
			bool allLoadsReplaced = true;
		};

		// Use the (unique) index of the alloca's destination argument (i.e. the address
		// of the allocated variable), which is of type SizeT, as the key. Note we do not
		// use the pointer to the alloca instruction or its resulting address, to avoid
		// undeterministic unordered_map behavior.
		std::unordered_map<Ice::SizeT, LastStore> lastStoreTo;

		for(Ice::Inst &inst : block->getInsts())
		{
			if(inst.isDeleted())
			{
				continue;
			}

			if(isStore(inst))
			{
				Ice::Operand *address = inst.getStoreAddress();

				if(Ice::InstAlloca *alloca = allocaOf(address))
				{
					// Only consider this store for propagation if its address is not used as
					// a pointer which could be used for indirect stores.
					if(getUses(address)->areOnlyLoadStore())
					{
						Ice::SizeT addressIdx = alloca->getDest()->getIndex();

						// If there was a previous store to this address, and it was propagated
						// to all subsequent loads, it can be eliminated.
						if(auto entry = lastStoreTo.find(addressIdx); entry != lastStoreTo.end())
						{
							Ice::Inst *previousStore = entry->second.store;

							if(storeTypeMatchesStore(&inst, previousStore) &&
							   entry->second.allLoadsReplaced)
							{
								deleteInstruction(previousStore);
							}
						}

						lastStoreTo[addressIdx] = { &inst };
					}
				}
			}
			else if(isLoad(inst))
			{
				if(Ice::InstAlloca *alloca = allocaOf(inst.getLoadAddress()))
				{
					Ice::SizeT addressIdx = alloca->getDest()->getIndex();
					auto entry = lastStoreTo.find(addressIdx);
					if(entry != lastStoreTo.end())
					{
						const Ice::Inst *store = entry->second.store;

						if(loadTypeMatchesStore(&inst, store))
						{
							replace(&inst, store->getData());
						}
						else
						{
							entry->second.allLoadsReplaced = false;
						}
					}
				}
			}
		}
	}

	// This can leave some dead instructions. Specifically stores.
	// TODO(b/179668593): Check just for dead stores by iterating over allocas?
	eliminateDeadCode();
}

void Optimizer::analyzeUses(Ice::Cfg *function)
{
	for(Ice::CfgNode *basicBlock : function->getNodes())
	{
		for(Ice::Inst &instruction : basicBlock->getInsts())
		{
			if(instruction.isDeleted())
			{
				continue;
			}

			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;
	}

	assert(!instruction->getDest() || getUses(instruction->getDest())->empty());
	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>(instruction->getStoreAddress()))
		{
			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::isStaticallyIndexedArray(Ice::Operand *allocaAddress)
{
	auto &uses = *getUses(allocaAddress);

	for(auto *use : uses)
	{
		// Direct load from base address.
		if(isLoad(*use) && use->getLoadAddress() == allocaAddress)
		{
			continue;  // This is fine.
		}

		if(isStore(*use))
		{
			// Can either be the address we're storing to, or the data we're storing.
			if(use->getStoreAddress() == allocaAddress)
			{
				continue;
			}
			else
			{
				// propagateAlloca() eliminates most of the stores of the address itself.
				// For the cases it doesn't handle, assume SRoA is not feasible.
				return false;
			}
		}

		// Pointer arithmetic is fine if it only uses constants.
		auto *arithmetic = llvm::dyn_cast<Ice::InstArithmetic>(use);
		if(arithmetic && arithmetic->getOp() == Ice::InstArithmetic::Add)
		{
			auto *rhs = arithmetic->getSrc(1);

			if(llvm::isa<Ice::Constant>(rhs))
			{
				continue;
			}
		}

		// If there's any other type of use, bail out.
		return false;
	}

	return true;
}

Ice::InstAlloca *Optimizer::allocaOf(Ice::Operand *address)
{
	Ice::Variable *addressVar = llvm::dyn_cast<Ice::Variable>(address);
	Ice::Inst *def = addressVar ? getDefinition(addressVar) : nullptr;
	Ice::InstAlloca *alloca = def ? llvm::dyn_cast<Ice::InstAlloca>(def) : nullptr;

	return alloca;
}

const Ice::InstIntrinsic *Optimizer::asLoadSubVector(const Ice::Inst *instruction)
{
	if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsic>(instruction))
	{
		if(instrinsic->getIntrinsicID() == Ice::Intrinsics::LoadSubVector)
		{
			return instrinsic;
		}
	}

	return nullptr;
}

const Ice::InstIntrinsic *Optimizer::asStoreSubVector(const Ice::Inst *instruction)
{
	if(auto *instrinsic = llvm::dyn_cast<Ice::InstIntrinsic>(instruction))
	{
		if(instrinsic->getIntrinsicID() == 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;
}

bool Optimizer::loadTypeMatchesStore(const Ice::Inst *load, const Ice::Inst *store)
{
	if(!load || !store)
	{
		return false;
	}

	assert(isLoad(*load) && isStore(*store));
	assert(load->getLoadAddress() == store->getStoreAddress());

	if(store->getData()->getType() != load->getDest()->getType())
	{
		return false;
	}

	if(auto *storeSubVector = asStoreSubVector(store))
	{
		if(auto *loadSubVector = asLoadSubVector(load))
		{
			// Check for matching sub-vector width.
			return llvm::cast<Ice::ConstantInteger32>(storeSubVector->getSrc(2))->getValue() ==
			       llvm::cast<Ice::ConstantInteger32>(loadSubVector->getSrc(1))->getValue();
		}
	}

	return true;
}

bool Optimizer::storeTypeMatchesStore(const Ice::Inst *store1, const Ice::Inst *store2)
{
	assert(isStore(*store1) && isStore(*store2));
	assert(store1->getStoreAddress() == store2->getStoreAddress());

	if(store1->getData()->getType() != store2->getData()->getType())
	{
		return false;
	}

	if(auto *storeSubVector1 = asStoreSubVector(store1))
	{
		if(auto *storeSubVector2 = asStoreSubVector(store2))
		{
			// Check for matching sub-vector width.
			return llvm::cast<Ice::ConstantInteger32>(storeSubVector1->getSrc(2))->getValue() ==
			       llvm::cast<Ice::ConstantInteger32>(storeSubVector2->getSrc(2))->getValue();
		}
	}

	return true;
}

void Optimizer::collectDiagnostics()
{
	if(report)
	{
		*report = {};

		for(auto *basicBlock : function->getNodes())
		{
			for(auto &inst : basicBlock->getInsts())
			{
				if(inst.isDeleted())
				{
					continue;
				}

				if(llvm::isa<Ice::InstAlloca>(inst))
				{
					report->allocas++;
				}
				else if(isLoad(inst))
				{
					report->loads++;
				}
				else if(isStore(inst))
				{
					report->stores++;
				}
			}
		}
	}
}

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);
		operandsWithUses.push_back(operand);
	}
	return uses;
}

void Optimizer::setUses(Ice::Operand *operand, Optimizer::Uses *uses)
{
	if(auto *oldUses = reinterpret_cast<Optimizer::Uses *>(operand->Ice::Operand::getExternalData()))
	{
		delete oldUses;
	}

	operand->Ice::Operand::setExternalData(uses);
}

bool Optimizer::hasUses(Ice::Operand *operand) const
{
	return operand->Ice::Operand::getExternalData() != nullptr;
}

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);
}

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 == instruction->getLoadAddress())
		{
			loads.push_back(instruction);
		}
	}
	else if(isStore(*instruction))
	{
		if(value == instruction->getStoreAddress())
		{
			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, Nucleus::OptimizerReport *report)
{
	Optimizer optimizer(report);

	optimizer.run(function);
}

}  // namespace rr