Merge pull request #5334 from ethereum/stringPerformance

[Yul] String performance

47 files changed, 271 insertions, 175 deletions

diff --git a/libyul/ASTDataForward.h b/libyul/ASTDataForward.h
index 7f131b5e..8c49e68f 100644
--- a/libyul/ASTDataForward.h
+++ b/libyul/ASTDataForward.h
@@ -46,6 +46,7 @@ using ExpressionStatement = solidity::assembly::ExpressionStatement;
 using Block = solidity::assembly::Block;
 
 using TypedName = solidity::assembly::TypedName;
+class YulString;
 
 using Expression = boost::variant<FunctionalInstruction, FunctionCall, Identifier, Literal>;
 using Statement = boost::variant<ExpressionStatement, Instruction, Label, StackAssignment, Assignment, VariableDeclaration, FunctionDefinition, If, Switch, ForLoop, Block>;
diff --git a/libyul/YulString.h b/libyul/YulString.h
new file mode 100644
index 00000000..ae01c83f
--- /dev/null
+++ b/libyul/YulString.h
@@ -0,0 +1,96 @@
+/*
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * String abstraction that avoids copies.
+ */
+
+#pragma once
+
+#include <boost/noncopyable.hpp>
+
+#include <map>
+#include <memory>
+#include <vector>
+#include <string>
+
+namespace dev
+{
+namespace yul
+{
+
+class YulStringRepository: boost::noncopyable
+{
+public:
+	YulStringRepository(): m_strings{std::make_shared<std::string>()}
+	{
+		m_ids[std::string{}] = 0;
+	}
+	static YulStringRepository& instance()
+	{
+		static YulStringRepository inst;
+		return inst;
+	}
+	size_t stringToId(std::string const& _string)
+	{
+		if (_string.empty())
+			return 0;
+		size_t& id = m_ids[_string];
+		if (id == 0)
+		{
+			m_strings.emplace_back(std::make_shared<std::string>(_string));
+			id = m_strings.size() - 1;
+		}
+		return id;
+	}
+	std::string const& idToString(size_t _id) const
+	{
+		return *m_strings.at(_id);
+	}
+
+private:
+	std::vector<std::shared_ptr<std::string>> m_strings;
+	std::map<std::string, size_t> m_ids;
+};
+
+class YulString
+{
+public:
+	YulString() = default;
+	explicit YulString(std::string const& _s): m_id(YulStringRepository::instance().stringToId(_s)) {}
+	YulString(YulString const&) = default;
+	YulString(YulString&&) = default;
+	YulString& operator=(YulString const&) = default;
+	YulString& operator=(YulString&&) = default;
+
+	/// This is not consistent with the string <-operator!
+	bool operator<(YulString const& _other) const { return m_id < _other.m_id; }
+	bool operator==(YulString const& _other) const { return m_id == _other.m_id; }
+	bool operator!=(YulString const& _other) const { return m_id != _other.m_id; }
+
+	bool empty() const { return m_id == 0; }
+	std::string const& str() const
+	{
+		return YulStringRepository::instance().idToString(m_id);
+	}
+
+private:
+	/// ID of the string. Assumes that the empty string has ID zero.
+	size_t m_id = 0;
+};
+
+}
+}
diff --git a/libyul/backends/evm/EVMCodeTransform.cpp b/libyul/backends/evm/EVMCodeTransform.cpp
index 89086b4e..650a8c0a 100644
--- a/libyul/backends/evm/EVMCodeTransform.cpp
+++ b/libyul/backends/evm/EVMCodeTransform.cpp
@@ -201,18 +201,18 @@ void CodeTransform::operator()(assembly::Literal const& _literal)
 {
 	m_assembly.setSourceLocation(_literal.location);
 	if (_literal.kind == assembly::LiteralKind::Number)
-		m_assembly.appendConstant(u256(_literal.value));
+		m_assembly.appendConstant(u256(_literal.value.str()));
 	else if (_literal.kind == assembly::LiteralKind::Boolean)
 	{
-		if (_literal.value == "true")
+		if (_literal.value.str() == "true")
 			m_assembly.appendConstant(u256(1));
 		else
 			m_assembly.appendConstant(u256(0));
 	}
 	else
 	{
-		solAssert(_literal.value.size() <= 32, "");
-		m_assembly.appendConstant(u256(h256(_literal.value, h256::FromBinary, h256::AlignLeft)));
+		solAssert(_literal.value.str().size() <= 32, "");
+		m_assembly.appendConstant(u256(h256(_literal.value.str(), h256::FromBinary, h256::AlignLeft)));
 	}
 	checkStackHeight(&_literal);
 }
@@ -454,13 +454,13 @@ AbstractAssembly::LabelID CodeTransform::labelID(Scope::Label const& _label)
 	return m_context->labelIDs[&_label];
 }
 
-AbstractAssembly::LabelID CodeTransform::functionEntryID(string const& _name, Scope::Function const& _function)
+AbstractAssembly::LabelID CodeTransform::functionEntryID(YulString _name, Scope::Function const& _function)
 {
 	if (!m_context->functionEntryIDs.count(&_function))
 	{
 		AbstractAssembly::LabelID id =
 			m_useNamedLabelsForFunctions ?
-			m_assembly.namedLabel(_name) :
+			m_assembly.namedLabel(_name.str()) :
 			m_assembly.newLabelId();
 		m_context->functionEntryIDs[&_function] = id;
 	}
diff --git a/libyul/backends/evm/EVMCodeTransform.h b/libyul/backends/evm/EVMCodeTransform.h
index 22ebbf43..c0de8ad6 100644
--- a/libyul/backends/evm/EVMCodeTransform.h
+++ b/libyul/backends/evm/EVMCodeTransform.h
@@ -117,7 +117,7 @@ private:
 	/// @returns the label ID corresponding to the given label, allocating a new one if
 	/// necessary.
 	AbstractAssembly::LabelID labelID(solidity::assembly::Scope::Label const& _label);
-	AbstractAssembly::LabelID functionEntryID(std::string const& _name, solidity::assembly::Scope::Function const& _function);
+	AbstractAssembly::LabelID functionEntryID(YulString _name, solidity::assembly::Scope::Function const& _function);
 	/// Generates code for an expression that is supposed to return a single value.
 	void visitExpression(Expression const& _expression);
 
diff --git a/libyul/optimiser/ASTCopier.cpp b/libyul/optimiser/ASTCopier.cpp
index 4b7f21f8..d0c8dd45 100644
--- a/libyul/optimiser/ASTCopier.cpp
+++ b/libyul/optimiser/ASTCopier.cpp
@@ -111,14 +111,14 @@ Statement ASTCopier::operator()(Switch const& _switch)
 
 Statement ASTCopier::operator()(FunctionDefinition const& _function)
 {
-	string translatedName = translateIdentifier(_function.name);
+	YulString translatedName = translateIdentifier(_function.name);
 
 	enterFunction(_function);
 	ScopeGuard g([&]() { this->leaveFunction(_function); });
 
 	return FunctionDefinition{
 		_function.location,
-		move(translatedName),
+		translatedName,
 		translateVector(_function.parameters),
 		translateVector(_function.returnVariables),
 		translate(_function.body)
diff --git a/libyul/optimiser/ASTCopier.h b/libyul/optimiser/ASTCopier.h
index 13369cef..b6aceee3 100644
--- a/libyul/optimiser/ASTCopier.h
+++ b/libyul/optimiser/ASTCopier.h
@@ -22,6 +22,8 @@
 
 #include <libyul/ASTDataForward.h>
 
+#include <libyul/YulString.h>
+
 #include <boost/variant.hpp>
 #include <boost/optional.hpp>
 
@@ -107,7 +109,7 @@ protected:
 	virtual void leaveScope(Block const&) { }
 	virtual void enterFunction(FunctionDefinition const&) { }
 	virtual void leaveFunction(FunctionDefinition const&) { }
-	virtual std::string translateIdentifier(std::string const& _name) { return _name; }
+	virtual YulString translateIdentifier(YulString _name) { return _name; }
 };
 
 template <typename T>
diff --git a/libyul/optimiser/ASTWalker.h b/libyul/optimiser/ASTWalker.h
index 41617d55..38cb85ea 100644
--- a/libyul/optimiser/ASTWalker.h
+++ b/libyul/optimiser/ASTWalker.h
@@ -23,6 +23,7 @@
 #include <libyul/ASTDataForward.h>
 
 #include <libyul/Exceptions.h>
+#include <libyul/YulString.h>
 
 #include <boost/variant.hpp>
 #include <boost/optional.hpp>
diff --git a/libyul/optimiser/CommonSubexpressionEliminator.cpp b/libyul/optimiser/CommonSubexpressionEliminator.cpp
index 51737097..64605362 100644
--- a/libyul/optimiser/CommonSubexpressionEliminator.cpp
+++ b/libyul/optimiser/CommonSubexpressionEliminator.cpp
@@ -43,13 +43,13 @@ void CommonSubexpressionEliminator::visit(Expression& _e)
 	if (_e.type() == typeid(Identifier))
 	{
 		Identifier& identifier = boost::get<Identifier>(_e);
-		string const& name = identifier.name;
+		YulString name = identifier.name;
 		if (m_value.count(name))
 		{
 			assertThrow(m_value.at(name), OptimizerException, "");
 			if (m_value.at(name)->type() == typeid(Identifier))
 			{
-				string const& value = boost::get<Identifier>(*m_value.at(name)).name;
+				YulString value = boost::get<Identifier>(*m_value.at(name)).name;
 				assertThrow(inScope(value), OptimizerException, "");
 				_e = Identifier{locationOf(_e), value};
 			}
diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp
index 7ac42c30..1ff1d2f0 100644
--- a/libyul/optimiser/DataFlowAnalyzer.cpp
+++ b/libyul/optimiser/DataFlowAnalyzer.cpp
@@ -38,9 +38,9 @@ using namespace dev::yul;
 
 void DataFlowAnalyzer::operator()(Assignment& _assignment)
 {
-	set<string> names;
+	set<YulString> names;
 	for (auto const& var: _assignment.variableNames)
-		names.insert(var.name);
+		names.emplace(var.name);
 	assertThrow(_assignment.value, OptimizerException, "");
 	visit(*_assignment.value);
 	handleAssignment(names, _assignment.value.get());
@@ -48,9 +48,9 @@ void DataFlowAnalyzer::operator()(Assignment& _assignment)
 
 void DataFlowAnalyzer::operator()(VariableDeclaration& _varDecl)
 {
-	set<string> names;
+	set<YulString> names;
 	for (auto const& var: _varDecl.variables)
-		names.insert(var.name);
+		names.emplace(var.name);
 	m_variableScopes.back().variables += names;
 	if (_varDecl.value)
 		visit(*_varDecl.value);
@@ -69,7 +69,7 @@ void DataFlowAnalyzer::operator()(If& _if)
 void DataFlowAnalyzer::operator()(Switch& _switch)
 {
 	visit(*_switch.expression);
-	set<string> assignedVariables;
+	set<YulString> assignedVariables;
 	for (auto& _case: _switch.cases)
 	{
 		(*this)(_case.body);
@@ -86,9 +86,9 @@ void DataFlowAnalyzer::operator()(FunctionDefinition& _fun)
 {
 	pushScope(true);
 	for (auto const& parameter: _fun.parameters)
-		m_variableScopes.back().variables.insert(parameter.name);
+		m_variableScopes.back().variables.emplace(parameter.name);
 	for (auto const& var: _fun.returnVariables)
-		m_variableScopes.back().variables.insert(var.name);
+		m_variableScopes.back().variables.emplace(var.name);
 	ASTModifier::operator()(_fun);
 	popScope();
 }
@@ -122,7 +122,7 @@ void DataFlowAnalyzer::operator()(Block& _block)
 	assertThrow(numScopes == m_variableScopes.size(), OptimizerException, "");
 }
 
-void DataFlowAnalyzer::handleAssignment(set<string> const& _variables, Expression* _value)
+void DataFlowAnalyzer::handleAssignment(set<YulString> const& _variables, Expression* _value)
 {
 	clearValues(_variables);
 
@@ -131,7 +131,7 @@ void DataFlowAnalyzer::handleAssignment(set<string> const& _variables, Expressio
 		movableChecker.visit(*_value);
 	if (_variables.size() == 1)
 	{
-		string const& name = *_variables.begin();
+		YulString name = *_variables.begin();
 		// Expression has to be movable and cannot contain a reference
 		// to the variable that will be assigned to.
 		if (_value && movableChecker.movable() && !movableChecker.referencedVariables().count(name))
@@ -143,7 +143,7 @@ void DataFlowAnalyzer::handleAssignment(set<string> const& _variables, Expressio
 	{
 		m_references[name] = referencedVariables;
 		for (auto const& ref: referencedVariables)
-			m_referencedBy[ref].insert(name);
+			m_referencedBy[ref].emplace(name);
 	}
 }
 
@@ -158,7 +158,7 @@ void DataFlowAnalyzer::popScope()
 	m_variableScopes.pop_back();
 }
 
-void DataFlowAnalyzer::clearValues(set<string> _variables)
+void DataFlowAnalyzer::clearValues(set<YulString> _variables)
 {
 	// All variables that reference variables to be cleared also have to be
 	// cleared, but not recursively, since only the value of the original
@@ -176,7 +176,7 @@ void DataFlowAnalyzer::clearValues(set<string> _variables)
 	// Clear variables that reference variables to be cleared.
 	for (auto const& name: _variables)
 		for (auto const& ref: m_referencedBy[name])
-			_variables.insert(ref);
+			_variables.emplace(ref);
 
 	// Clear the value and update the reference relation.
 	for (auto const& name: _variables)
@@ -189,7 +189,7 @@ void DataFlowAnalyzer::clearValues(set<string> _variables)
 	}
 }
 
-bool DataFlowAnalyzer::inScope(string const& _variableName) const
+bool DataFlowAnalyzer::inScope(YulString _variableName) const
 {
 	for (auto const& scope: m_variableScopes | boost::adaptors::reversed)
 	{
diff --git a/libyul/optimiser/DataFlowAnalyzer.h b/libyul/optimiser/DataFlowAnalyzer.h
index 95671467..a0c21eee 100644
--- a/libyul/optimiser/DataFlowAnalyzer.h
+++ b/libyul/optimiser/DataFlowAnalyzer.h
@@ -24,7 +24,8 @@
 
 #include <libyul/optimiser/ASTWalker.h>
 
-#include <string>
+#include <libyul/YulString.h>
+
 #include <map>
 #include <set>
 
@@ -54,7 +55,7 @@ public:
 
 protected:
 	/// Registers the assignment.
-	void handleAssignment(std::set<std::string> const& _names, Expression* _value);
+	void handleAssignment(std::set<YulString> const& _names, Expression* _value);
 
 	/// Creates a new inner scope.
 	void pushScope(bool _functionScope);
@@ -64,22 +65,22 @@ protected:
 
 	/// Clears information about the values assigned to the given variables,
 	/// for example at points where control flow is merged.
-	void clearValues(std::set<std::string> _names);
+	void clearValues(std::set<YulString> _names);
 
 	/// Returns true iff the variable is in scope.
-	bool inScope(std::string const& _variableName) const;
+	bool inScope(YulString _variableName) const;
 
 	/// Current values of variables, always movable.
-	std::map<std::string, Expression const*> m_value;
+	std::map<YulString, Expression const*> m_value;
 	/// m_references[a].contains(b) <=> the current expression assigned to a references b
-	std::map<std::string, std::set<std::string>> m_references;
+	std::map<YulString, std::set<YulString>> m_references;
 	/// m_referencedBy[b].contains(a) <=> the current expression assigned to a references b
-	std::map<std::string, std::set<std::string>> m_referencedBy;
+	std::map<YulString, std::set<YulString>> m_referencedBy;
 
 	struct Scope
 	{
 		explicit Scope(bool _isFunction): isFunction(_isFunction) {}
-		std::set<std::string> variables;
+		std::set<YulString> variables;
 		bool isFunction;
 	};
 	/// List of scopes.
diff --git a/libyul/optimiser/Disambiguator.cpp b/libyul/optimiser/Disambiguator.cpp
index dcba97c9..4303f412 100644
--- a/libyul/optimiser/Disambiguator.cpp
+++ b/libyul/optimiser/Disambiguator.cpp
@@ -32,7 +32,7 @@ using namespace dev::solidity;
 
 using Scope = dev::solidity::assembly::Scope;
 
-string Disambiguator::translateIdentifier(string const& _originalName)
+YulString Disambiguator::translateIdentifier(YulString _originalName)
 {
 	if ((m_externallyUsedIdentifiers.count(_originalName)))
 		return _originalName;
diff --git a/libyul/optimiser/Disambiguator.h b/libyul/optimiser/Disambiguator.h
index 74a491ab..bfb65682 100644
--- a/libyul/optimiser/Disambiguator.h
+++ b/libyul/optimiser/Disambiguator.h
@@ -45,7 +45,7 @@ class Disambiguator: public ASTCopier
 public:
 	explicit Disambiguator(
 		solidity::assembly::AsmAnalysisInfo const& _analysisInfo,
-		std::set<std::string> const& _externallyUsedIdentifiers = {}
+		std::set<YulString> const& _externallyUsedIdentifiers = {}
 	):
 		m_info(_analysisInfo), m_externallyUsedIdentifiers(_externallyUsedIdentifiers), m_nameDispenser(m_externallyUsedIdentifiers)
 	{
@@ -56,16 +56,16 @@ protected:
 	virtual void leaveScope(Block const& _block) override;
 	virtual void enterFunction(FunctionDefinition const& _function) override;
 	virtual void leaveFunction(FunctionDefinition const& _function) override;
-	virtual std::string translateIdentifier(std::string const& _name) override;
+	virtual YulString translateIdentifier(YulString _name) override;
 
 	void enterScopeInternal(solidity::assembly::Scope& _scope);
 	void leaveScopeInternal(solidity::assembly::Scope& _scope);
 
 	solidity::assembly::AsmAnalysisInfo const& m_info;
-	std::set<std::string> const& m_externallyUsedIdentifiers;
+	std::set<YulString> const& m_externallyUsedIdentifiers;
 
 	std::vector<solidity::assembly::Scope*> m_scopes;
-	std::map<void const*, std::string> m_translations;
+	std::map<void const*, YulString> m_translations;
 	NameDispenser m_nameDispenser;
 };
 
diff --git a/libyul/optimiser/ExpressionInliner.cpp b/libyul/optimiser/ExpressionInliner.cpp
index 9bf0a3fb..07e88191 100644
--- a/libyul/optimiser/ExpressionInliner.cpp
+++ b/libyul/optimiser/ExpressionInliner.cpp
@@ -62,7 +62,7 @@ void ExpressionInliner::visit(Expression& _expression)
 		if (m_inlinableFunctions.count(funCall.functionName.name) && movable)
 		{
 			FunctionDefinition const& fun = *m_inlinableFunctions.at(funCall.functionName.name);
-			map<string, Expression const*> substitutions;
+			map<YulString, Expression const*> substitutions;
 			for (size_t i = 0; i < fun.parameters.size(); ++i)
 				substitutions[fun.parameters[i].name] = &funCall.arguments[i];
 			_expression = Substitution(substitutions).translate(*boost::get<Assignment>(fun.body.statements.front()).value);
diff --git a/libyul/optimiser/ExpressionInliner.h b/libyul/optimiser/ExpressionInliner.h
index 971a2ee0..d903664f 100644
--- a/libyul/optimiser/ExpressionInliner.h
+++ b/libyul/optimiser/ExpressionInliner.h
@@ -59,10 +59,10 @@ public:
 	virtual void visit(Expression& _expression) override;
 
 private:
-	std::map<std::string, FunctionDefinition const*> m_inlinableFunctions;
-	std::map<std::string, std::string> m_varReplacements;
+	std::map<YulString, FunctionDefinition const*> m_inlinableFunctions;
+	std::map<YulString, YulString> m_varReplacements;
 	/// Set of functions we are currently visiting inside.
-	std::set<std::string> m_currentFunctions;
+	std::set<YulString> m_currentFunctions;
 
 	Block& m_block;
 };
diff --git a/libyul/optimiser/ExpressionJoiner.h b/libyul/optimiser/ExpressionJoiner.h
index 4f06cc0f..0cc61981 100644
--- a/libyul/optimiser/ExpressionJoiner.h
+++ b/libyul/optimiser/ExpressionJoiner.h
@@ -93,9 +93,9 @@ private:
 	bool isLatestStatementVarDeclJoinable(Identifier const& _identifier);
 
 private:
-	Block* m_currentBlock = nullptr;            ///< Pointer to currently block holding the visiting statement.
-	size_t m_latestStatementInBlock = 0;        ///< Offset to m_currentBlock's statements of the last visited statement.
-	std::map<std::string, size_t> m_references; ///< Holds reference counts to all variable declarations in current block.
+	Block* m_currentBlock = nullptr;		///< Pointer to current block holding the statement being visited.
+	size_t m_latestStatementInBlock = 0;		///< Offset to m_currentBlock's statements of the last visited statement.
+	std::map<YulString, size_t> m_references;	///< Holds reference counts to all variable declarations in current block.
 };
 
 }
diff --git a/libyul/optimiser/ExpressionSimplifier.h b/libyul/optimiser/ExpressionSimplifier.h
index 5419ff6a..5965a1bb 100644
--- a/libyul/optimiser/ExpressionSimplifier.h
+++ b/libyul/optimiser/ExpressionSimplifier.h
@@ -44,11 +44,11 @@ public:
 
 	static void run(Block& _ast);
 private:
-	explicit ExpressionSimplifier(std::map<std::string, Expression const*> _ssaValues):
+	explicit ExpressionSimplifier(std::map<YulString, Expression const*> _ssaValues):
 		m_ssaValues(std::move(_ssaValues))
 	{}
 
-	std::map<std::string, Expression const*> m_ssaValues;
+	std::map<YulString, Expression const*> m_ssaValues;
 };
 
 }
diff --git a/libyul/optimiser/ExpressionSplitter.cpp b/libyul/optimiser/ExpressionSplitter.cpp
index a2ecc546..a4b7a909 100644
--- a/libyul/optimiser/ExpressionSplitter.cpp
+++ b/libyul/optimiser/ExpressionSplitter.cpp
@@ -95,10 +95,10 @@ void ExpressionSplitter::outlineExpression(Expression& _expr)
 	visit(_expr);
 
 	SourceLocation location = locationOf(_expr);
-	string var = m_nameDispenser.newName("");
+	YulString var = m_nameDispenser.newName({});
 	m_statementsToPrefix.emplace_back(VariableDeclaration{
 		location,
-		{{TypedName{location, var, ""}}},
+		{{TypedName{location, var, {}}}},
 		make_shared<Expression>(std::move(_expr))
 	});
 	_expr = Identifier{location, var};
diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp
index 280d625a..c9057cf3 100644
--- a/libyul/optimiser/FullInliner.cpp
+++ b/libyul/optimiser/FullInliner.cpp
@@ -48,9 +48,9 @@ FullInliner::FullInliner(Block& _ast, NameDispenser& _dispenser):
 	tracker(m_ast);
 	for (auto const& ssaValue: tracker.values())
 		if (ssaValue.second && ssaValue.second->type() == typeid(Literal))
-			m_constants.insert(ssaValue.first);
+			m_constants.emplace(ssaValue.first);
 
-	map<string, size_t> references = ReferencesCounter::countReferences(m_ast);
+	map<YulString, size_t> references = ReferencesCounter::countReferences(m_ast);
 	for (auto& statement: m_ast.statements)
 	{
 		if (statement.type() != typeid(FunctionDefinition))
@@ -59,7 +59,7 @@ FullInliner::FullInliner(Block& _ast, NameDispenser& _dispenser):
 		m_functions[fun.name] = &fun;
 		// Always inline functions that are only called once.
 		if (references[fun.name] == 1)
-			m_alwaysInline.insert(fun.name);
+			m_alwaysInline.emplace(fun.name);
 		updateCodeSize(fun);
 	}
 }
@@ -68,7 +68,7 @@ void FullInliner::run()
 {
 	for (auto& statement: m_ast.statements)
 		if (statement.type() == typeid(Block))
-			handleBlock("", boost::get<Block>(statement));
+			handleBlock({}, boost::get<Block>(statement));
 
 	// TODO it might be good to determine a visiting order:
 	// first handle functions that are called from many places.
@@ -84,12 +84,12 @@ void FullInliner::updateCodeSize(FunctionDefinition& fun)
 	m_functionSizes[fun.name] = CodeSize::codeSize(fun.body);
 }
 
-void FullInliner::handleBlock(string const& _currentFunctionName, Block& _block)
+void FullInliner::handleBlock(YulString _currentFunctionName, Block& _block)
 {
 	InlineModifier{*this, m_nameDispenser, _currentFunctionName}(_block);
 }
 
-bool FullInliner::shallInline(FunctionCall const& _funCall, string const& _callSite)
+bool FullInliner::shallInline(FunctionCall const& _funCall, YulString _callSite)
 {
 	// No recursive inlining
 	if (_funCall.functionName.name == _callSite)
@@ -148,14 +148,14 @@ boost::optional<vector<Statement>> InlineModifier::tryInlineStatement(Statement&
 vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionCall& _funCall)
 {
 	vector<Statement> newStatements;
-	map<string, string> variableReplacements;
+	map<YulString, YulString> variableReplacements;
 
 	FunctionDefinition& function = m_driver.function(_funCall.functionName.name);
 
 	// helper function to create a new variable that is supposed to model
 	// an existing variable.
 	auto newVariable = [&](TypedName const& _existingVariable, Expression* _value) {
-		string newName = m_nameDispenser.newName(_existingVariable.name, function.name);
+		YulString newName = m_nameDispenser.newName(_existingVariable.name, function.name);
 		variableReplacements[_existingVariable.name] = newName;
 		VariableDeclaration varDecl{_funCall.location, {{_funCall.location, newName, _existingVariable.type}}, {}};
 		if (_value)
@@ -214,7 +214,7 @@ Statement BodyCopier::operator()(FunctionDefinition const& _funDef)
 	return _funDef;
 }
 
-string BodyCopier::translateIdentifier(string const& _name)
+YulString BodyCopier::translateIdentifier(YulString _name)
 {
 	if (m_variableReplacements.count(_name))
 		return m_variableReplacements.at(_name);
diff --git a/libyul/optimiser/FullInliner.h b/libyul/optimiser/FullInliner.h
index 5ecfb57a..66ce8e2f 100644
--- a/libyul/optimiser/FullInliner.h
+++ b/libyul/optimiser/FullInliner.h
@@ -77,23 +77,23 @@ public:
 
 	/// Inlining heuristic.
 	/// @param _callSite the name of the function in which the function call is located.
-	bool shallInline(FunctionCall const& _funCall, std::string const& _callSite);
+	bool shallInline(FunctionCall const& _funCall, YulString _callSite);
 
-	FunctionDefinition& function(std::string _name) { return *m_functions.at(_name); }
+	FunctionDefinition& function(YulString _name) { return *m_functions.at(_name); }
 
 private:
 	void updateCodeSize(FunctionDefinition& fun);
-	void handleBlock(std::string const& _currentFunctionName, Block& _block);
+	void handleBlock(YulString _currentFunctionName, Block& _block);
 
 	/// The AST to be modified. The root block itself will not be modified, because
 	/// we store pointers to functions.
 	Block& m_ast;
-	std::map<std::string, FunctionDefinition*> m_functions;
+	std::map<YulString, FunctionDefinition*> m_functions;
 	/// Names of functions to always inline.
-	std::set<std::string> m_alwaysInline;
+	std::set<YulString> m_alwaysInline;
 	/// Variables that are constants (used for inlining heuristic)
-	std::set<std::string> m_constants;
-	std::map<std::string, size_t> m_functionSizes;
+	std::set<YulString> m_constants;
+	std::map<YulString, size_t> m_functionSizes;
 	NameDispenser& m_nameDispenser;
 };
 
@@ -104,7 +104,7 @@ private:
 class InlineModifier: public ASTModifier
 {
 public:
-	InlineModifier(FullInliner& _driver, NameDispenser& _nameDispenser, std::string _functionName):
+	InlineModifier(FullInliner& _driver, NameDispenser& _nameDispenser, YulString _functionName):
 		m_currentFunction(std::move(_functionName)),
 		m_driver(_driver),
 		m_nameDispenser(_nameDispenser)
@@ -116,7 +116,7 @@ private:
 	boost::optional<std::vector<Statement>> tryInlineStatement(Statement& _statement);
 	std::vector<Statement> performInline(Statement& _statement, FunctionCall& _funCall);
 
-	std::string m_currentFunction;
+	YulString m_currentFunction;
 	FullInliner& m_driver;
 	NameDispenser& m_nameDispenser;
 };
@@ -131,8 +131,8 @@ class BodyCopier: public ASTCopier
 public:
 	BodyCopier(
 		NameDispenser& _nameDispenser,
-		std::string const& _varNamePrefix,
-		std::map<std::string, std::string> const& _variableReplacements
+		YulString _varNamePrefix,
+		std::map<YulString, YulString> const& _variableReplacements
 	):
 		m_nameDispenser(_nameDispenser),
 		m_varNamePrefix(_varNamePrefix),
@@ -144,11 +144,11 @@ public:
 	virtual Statement operator()(VariableDeclaration const& _varDecl) override;
 	virtual Statement operator()(FunctionDefinition const& _funDef) override;
 
-	virtual std::string translateIdentifier(std::string const& _name) override;
+	virtual YulString translateIdentifier(YulString _name) override;
 
 	NameDispenser& m_nameDispenser;
-	std::string const& m_varNamePrefix;
-	std::map<std::string, std::string> m_variableReplacements;
+	YulString m_varNamePrefix;
+	std::map<YulString, YulString> m_variableReplacements;
 };
 
 
diff --git a/libyul/optimiser/InlinableExpressionFunctionFinder.cpp b/libyul/optimiser/InlinableExpressionFunctionFinder.cpp
index 69dd2095..deaaee97 100644
--- a/libyul/optimiser/InlinableExpressionFunctionFinder.cpp
+++ b/libyul/optimiser/InlinableExpressionFunctionFinder.cpp
@@ -44,7 +44,7 @@ void InlinableExpressionFunctionFinder::operator()(FunctionDefinition const& _fu
 {
 	if (_function.returnVariables.size() == 1 && _function.body.statements.size() == 1)
 	{
-		string const& retVariable = _function.returnVariables.front().name;
+		YulString retVariable = _function.returnVariables.front().name;
 		Statement const& bodyStatement = _function.body.statements.front();
 		if (bodyStatement.type() == typeid(Assignment))
 		{
@@ -57,7 +57,7 @@ void InlinableExpressionFunctionFinder::operator()(FunctionDefinition const& _fu
 				// would not be valid here if we were searching inside a functionally inlinable
 				// function body.
 				assertThrow(m_disallowedIdentifiers.empty() && !m_foundDisallowedIdentifier, OptimizerException, "");
-				m_disallowedIdentifiers = set<string>{retVariable, _function.name};
+				m_disallowedIdentifiers = set<YulString>{retVariable, _function.name};
 				boost::apply_visitor(*this, *assignment.value);
 				if (!m_foundDisallowedIdentifier)
 					m_inlinableFunctions[_function.name] = &_function;
diff --git a/libyul/optimiser/InlinableExpressionFunctionFinder.h b/libyul/optimiser/InlinableExpressionFunctionFinder.h
index 3887e6e5..baf4bbfc 100644
--- a/libyul/optimiser/InlinableExpressionFunctionFinder.h
+++ b/libyul/optimiser/InlinableExpressionFunctionFinder.h
@@ -43,7 +43,7 @@ class InlinableExpressionFunctionFinder: public ASTWalker
 {
 public:
 
-	std::map<std::string, FunctionDefinition const*> const& inlinableFunctions() const
+	std::map<YulString, FunctionDefinition const*> const& inlinableFunctions() const
 	{
 		return m_inlinableFunctions;
 	}
@@ -54,15 +54,15 @@ public:
 	virtual void operator()(FunctionDefinition const& _function) override;
 
 private:
-	void checkAllowed(std::string const& _name)
+	void checkAllowed(YulString _name)
 	{
 		if (m_disallowedIdentifiers.count(_name))
 			m_foundDisallowedIdentifier = true;
 	}
 
 	bool m_foundDisallowedIdentifier = false;
-	std::set<std::string> m_disallowedIdentifiers;
-	std::map<std::string, FunctionDefinition const*> m_inlinableFunctions;
+	std::set<YulString> m_disallowedIdentifiers;
+	std::map<YulString, FunctionDefinition const*> m_inlinableFunctions;
 };
 
 }
diff --git a/libyul/optimiser/MainFunction.cpp b/libyul/optimiser/MainFunction.cpp
index c8f35207..f3306598 100644
--- a/libyul/optimiser/MainFunction.cpp
+++ b/libyul/optimiser/MainFunction.cpp
@@ -40,12 +40,12 @@ void MainFunction::operator()(Block& _block)
 	for (size_t i = 1; i < _block.statements.size(); ++i)
 		assertThrow(_block.statements.at(i).type() == typeid(FunctionDefinition), OptimizerException, "");
 	/// @todo this should handle scopes properly and instead of an assertion it should rename the conflicting function
-	assertThrow(NameCollector(_block).names().count("main") == 0, OptimizerException, "");
+	assertThrow(NameCollector(_block).names().count(YulString{"main"}) == 0, OptimizerException, "");
 
 	Block& block = boost::get<Block>(_block.statements[0]);
 	FunctionDefinition main{
 		block.location,
-		"main",
+		YulString{"main"},
 		{},
 		{},
 		std::move(block)
diff --git a/libyul/optimiser/NameCollector.cpp b/libyul/optimiser/NameCollector.cpp
index b71fa982..36f55b99 100644
--- a/libyul/optimiser/NameCollector.cpp
+++ b/libyul/optimiser/NameCollector.cpp
@@ -29,16 +29,16 @@ using namespace dev::yul;
 void NameCollector::operator()(VariableDeclaration const& _varDecl)
 {
 	for (auto const& var: _varDecl.variables)
-		m_names.insert(var.name);
+		m_names.emplace(var.name);
 }
 
 void NameCollector::operator ()(FunctionDefinition const& _funDef)
 {
-	m_names.insert(_funDef.name);
+	m_names.emplace(_funDef.name);
 	for (auto const arg: _funDef.parameters)
-		m_names.insert(arg.name);
+		m_names.emplace(arg.name);
 	for (auto const ret: _funDef.returnVariables)
-		m_names.insert(ret.name);
+		m_names.emplace(ret.name);
 	ASTWalker::operator ()(_funDef);
 }
 
@@ -53,14 +53,14 @@ void ReferencesCounter::operator()(FunctionCall const& _funCall)
 	ASTWalker::operator()(_funCall);
 }
 
-map<string, size_t> ReferencesCounter::countReferences(Block const& _block)
+map<YulString, size_t> ReferencesCounter::countReferences(Block const& _block)
 {
 	ReferencesCounter counter;
 	counter(_block);
 	return counter.references();
 }
 
-map<string, size_t> ReferencesCounter::countReferences(Expression const& _expression)
+map<YulString, size_t> ReferencesCounter::countReferences(Expression const& _expression)
 {
 	ReferencesCounter counter;
 	counter.visit(_expression);
@@ -70,5 +70,5 @@ map<string, size_t> ReferencesCounter::countReferences(Expression const& _expres
 void Assignments::operator()(Assignment const& _assignment)
 {
 	for (auto const& var: _assignment.variableNames)
-		m_names.insert(var.name);
+		m_names.emplace(var.name);
 }
diff --git a/libyul/optimiser/NameCollector.h b/libyul/optimiser/NameCollector.h
index b8f6c1d7..b76eec30 100644
--- a/libyul/optimiser/NameCollector.h
+++ b/libyul/optimiser/NameCollector.h
@@ -22,7 +22,6 @@
 
 #include <libyul/optimiser/ASTWalker.h>
 
-#include <string>
 #include <map>
 #include <set>
 
@@ -46,9 +45,9 @@ public:
 	virtual void operator()(VariableDeclaration const& _varDecl) override;
 	virtual void operator()(FunctionDefinition const& _funDef) override;
 
-	std::set<std::string> names() const { return m_names; }
+	std::set<YulString> names() const { return m_names; }
 private:
-	std::set<std::string> m_names;
+	std::set<YulString> m_names;
 };
 
 /**
@@ -61,12 +60,12 @@ public:
 	virtual void operator()(Identifier const& _identifier);
 	virtual void operator()(FunctionCall const& _funCall);
 
-	static std::map<std::string, size_t> countReferences(Block const& _block);
-	static std::map<std::string, size_t> countReferences(Expression const& _expression);
+	static std::map<YulString, size_t> countReferences(Block const& _block);
+	static std::map<YulString, size_t> countReferences(Expression const& _expression);
 
-	std::map<std::string, size_t> const& references() const { return m_references; }
+	std::map<YulString, size_t> const& references() const { return m_references; }
 private:
-	std::map<std::string, size_t> m_references;
+	std::map<YulString, size_t> m_references;
 };
 
 /**
@@ -78,9 +77,9 @@ public:
 	using ASTWalker::operator ();
 	virtual void operator()(Assignment const& _assignment) override;
 
-	std::set<std::string> const& names() const { return m_names; }
+	std::set<YulString> const& names() const { return m_names; }
 private:
-	std::set<std::string> m_names;
+	std::set<YulString> m_names;
 };
 
 }
diff --git a/libyul/optimiser/NameDispenser.cpp b/libyul/optimiser/NameDispenser.cpp
index d3f10bc2..492c863d 100644
--- a/libyul/optimiser/NameDispenser.cpp
+++ b/libyul/optimiser/NameDispenser.cpp
@@ -33,31 +33,31 @@ NameDispenser::NameDispenser(Block const& _ast):
 {
 }
 
-NameDispenser::NameDispenser(set<string> _usedNames):
+NameDispenser::NameDispenser(set<YulString> _usedNames):
 	m_usedNames(std::move(_usedNames))
 {
 }
 
-string NameDispenser::newName(string const& _nameHint, string const& _context)
+YulString NameDispenser::newName(YulString _nameHint, YulString _context)
 {
 	// Shortening rules: Use a suffix of _prefix and a prefix of _context.
-	string prefix = _nameHint;
+	YulString prefix = _nameHint;
 
 	if (!_context.empty())
-		prefix = _context.substr(0, 10) + "_" + prefix;
+		prefix = YulString{_context.str().substr(0, 10) + "_" + prefix.str()};
 
 	return newNameInternal(prefix);
 }
 
-string NameDispenser::newNameInternal(string const& _nameHint)
+YulString NameDispenser::newNameInternal(YulString _nameHint)
 {
+	YulString name = _nameHint;
 	size_t suffix = 0;
-	string name = _nameHint;
 	while (name.empty() || m_usedNames.count(name))
 	{
 		suffix++;
-		name = _nameHint + "_" + to_string(suffix);
+		name = YulString(_nameHint.str() + "_" + to_string(suffix));
 	}
-	m_usedNames.insert(name);
+	m_usedNames.emplace(name);
 	return name;
 }
diff --git a/libyul/optimiser/NameDispenser.h b/libyul/optimiser/NameDispenser.h
index 5fbf5f8e..57adbcad 100644
--- a/libyul/optimiser/NameDispenser.h
+++ b/libyul/optimiser/NameDispenser.h
@@ -21,8 +21,9 @@
 
 #include <libyul/ASTDataForward.h>
 
+#include <libyul/YulString.h>
+
 #include <set>
-#include <string>
 
 namespace dev
 {
@@ -41,18 +42,18 @@ public:
 	/// Initialize the name dispenser with all the names used in the given AST.
 	explicit NameDispenser(Block const& _ast);
 	/// Initialize the name dispenser with the given used names.
-	explicit NameDispenser(std::set<std::string> _usedNames);
+	explicit NameDispenser(std::set<YulString> _usedNames);
 
 	/// @returns a currently unused name that should be similar to _nameHint
 	/// and prefixed by _context if present.
 	/// If the resulting name would be too long, trims the context at the end
 	/// and the name hint at the start.
-	std::string newName(std::string const& _nameHint, std::string const& _context = {});
+	YulString newName(YulString _nameHint, YulString _context = {});
 
 private:
-	std::string newNameInternal(std::string const& _nameHint);
+	YulString newNameInternal(YulString _nameHint);
 
-	std::set<std::string> m_usedNames;
+	std::set<YulString> m_usedNames;
 };
 
 }
diff --git a/libyul/optimiser/RedundantAssignEliminator.cpp b/libyul/optimiser/RedundantAssignEliminator.cpp
index 478858e4..775b7673 100644
--- a/libyul/optimiser/RedundantAssignEliminator.cpp
+++ b/libyul/optimiser/RedundantAssignEliminator.cpp
@@ -44,7 +44,7 @@ void RedundantAssignEliminator::operator()(VariableDeclaration const& _variableD
 	ASTWalker::operator()(_variableDeclaration);
 
 	for (auto const& var: _variableDeclaration.variables)
-		m_declaredVariables.insert(var.name);
+		m_declaredVariables.emplace(var.name);
 }
 
 void RedundantAssignEliminator::operator()(Assignment const& _assignment)
@@ -156,7 +156,7 @@ void RedundantAssignEliminator::run(Block& _ast)
 		{
 			assertThrow(assignment.second != State::Undecided, OptimizerException, "");
 			if (assignment.second == State::Unused && MovableChecker{*assignment.first->value}.movable())
-				assignmentsToRemove.insert(assignment.first);
+				assignmentsToRemove.emplace(assignment.first);
 		}
 
 	AssignmentRemover remover{assignmentsToRemove};
@@ -176,7 +176,7 @@ void RedundantAssignEliminator::join(RedundantAssignEliminator& _other)
 			m_assignments[var.first] = std::move(var.second);
 }
 
-void RedundantAssignEliminator::changeUndecidedTo(string const& _variable, RedundantAssignEliminator::State _newState)
+void RedundantAssignEliminator::changeUndecidedTo(YulString _variable, RedundantAssignEliminator::State _newState)
 {
 	for (auto& assignment: m_assignments[_variable])
 		if (assignment.second == State{State::Undecided})
diff --git a/libyul/optimiser/RedundantAssignEliminator.h b/libyul/optimiser/RedundantAssignEliminator.h
index 52092138..805a1f63 100644
--- a/libyul/optimiser/RedundantAssignEliminator.h
+++ b/libyul/optimiser/RedundantAssignEliminator.h
@@ -125,9 +125,9 @@ private:
 	public:
 		enum Value { Unused, Undecided, Used };
 		State(Value _value = Undecided): m_value(_value) {}
-		bool operator==(State _other) const { return m_value == _other.m_value; }
-		bool operator!=(State _other) const { return !operator==(_other); }
-		void join(State _other)
+		inline bool operator==(State _other) const { return m_value == _other.m_value; }
+		inline bool operator!=(State _other) const { return !operator==(_other); }
+		inline void join(State const& _other)
 		{
 			// Using "max" works here because of the order of the values in the enum.
 			m_value = Value(std::max(int(_other.m_value), int(m_value)));
@@ -156,17 +156,18 @@ private:
 
 	private:
 		RedundantAssignEliminator& m_rae;
-		std::set<std::string> m_outerDeclaredVariables;
+		std::set<YulString> m_outerDeclaredVariables;
 	};
 
 	/// Joins the assignment mapping with @a _other according to the rules laid out
 	/// above.
 	/// Will destroy @a _other.
 	void join(RedundantAssignEliminator& _other);
-	void changeUndecidedTo(std::string const& _variable, State _newState);
+	void changeUndecidedTo(YulString _variable, State _newState);
 
-	std::set<std::string> m_declaredVariables;
-	std::map<std::string, std::map<Assignment const*, State>> m_assignments;
+	std::set<YulString> m_declaredVariables;
+	// TODO check that this does not cause nondeterminism!
+	std::map<YulString, std::map<Assignment const*, State>> m_assignments;
 };
 
 class AssignmentRemover: public ASTModifier
diff --git a/libyul/optimiser/Rematerialiser.cpp b/libyul/optimiser/Rematerialiser.cpp
index a99db0b6..38d50ef4 100644
--- a/libyul/optimiser/Rematerialiser.cpp
+++ b/libyul/optimiser/Rematerialiser.cpp
@@ -37,7 +37,7 @@ void Rematerialiser::visit(Expression& _e)
 		Identifier& identifier = boost::get<Identifier>(_e);
 		if (m_value.count(identifier.name))
 		{
-			string name = identifier.name;
+			YulString name = identifier.name;
 			for (auto const& ref: m_references[name])
 				assertThrow(inScope(ref), OptimizerException, "");
 			assertThrow(m_value.at(name), OptimizerException, "");
diff --git a/libyul/optimiser/Rematerialiser.h b/libyul/optimiser/Rematerialiser.h
index afcfab3e..f82465eb 100644
--- a/libyul/optimiser/Rematerialiser.h
+++ b/libyul/optimiser/Rematerialiser.h
@@ -22,10 +22,6 @@
 
 #include <libyul/optimiser/DataFlowAnalyzer.h>
 
-#include <string>
-#include <map>
-#include <set>
-
 namespace dev
 {
 namespace yul
diff --git a/libyul/optimiser/SSATransform.cpp b/libyul/optimiser/SSATransform.cpp
index 9db7bd03..f209ee7b 100644
--- a/libyul/optimiser/SSATransform.cpp
+++ b/libyul/optimiser/SSATransform.cpp
@@ -62,15 +62,15 @@ void SSATransform::operator()(ForLoop& _for)
 
 void SSATransform::operator()(Block& _block)
 {
-	set<string> variablesToClearAtEnd;
+	set<YulString> variablesToClearAtEnd;
 
 	// Creates a new variable (and returns its declaration) with value _value
 	// and replaces _value by a reference to that new variable.
-	auto replaceByNew = [&](SourceLocation _loc, string _varName, string _type, shared_ptr<Expression>& _value) -> VariableDeclaration
+	auto replaceByNew = [&](SourceLocation _loc, YulString _varName, YulString _type, shared_ptr<Expression>& _value) -> VariableDeclaration
 	{
-		string newName = m_nameDispenser.newName(_varName);
+		YulString newName = m_nameDispenser.newName(_varName);
 		m_currentVariableValues[_varName] = newName;
-		variablesToClearAtEnd.insert(_varName);
+		variablesToClearAtEnd.emplace(_varName);
 		shared_ptr<Expression> v = make_shared<Expression>(Identifier{_loc, newName});
 		_value.swap(v);
 		return VariableDeclaration{_loc, {TypedName{_loc, std::move(newName), std::move(_type)}}, std::move(v)};
diff --git a/libyul/optimiser/SSATransform.h b/libyul/optimiser/SSATransform.h
index 2adc657d..bb642549 100644
--- a/libyul/optimiser/SSATransform.h
+++ b/libyul/optimiser/SSATransform.h
@@ -85,13 +85,13 @@ public:
 	static void run(Block& _ast, NameDispenser& _nameDispenser);
 
 private:
-	explicit SSATransform(NameDispenser& _nameDispenser, std::set<std::string> const& _variablesToReplace):
+	explicit SSATransform(NameDispenser& _nameDispenser, std::set<YulString> const& _variablesToReplace):
 		m_nameDispenser(_nameDispenser), m_variablesToReplace(_variablesToReplace)
 	{ }
 
 	NameDispenser& m_nameDispenser;
-	std::set<std::string> const& m_variablesToReplace;
-	std::map<std::string, std::string> m_currentVariableValues;
+	std::set<YulString> const& m_variablesToReplace;
+	std::map<YulString, YulString> m_currentVariableValues;
 };
 
 }
diff --git a/libyul/optimiser/SSAValueTracker.cpp b/libyul/optimiser/SSAValueTracker.cpp
index a1291d67..491117da 100644
--- a/libyul/optimiser/SSAValueTracker.cpp
+++ b/libyul/optimiser/SSAValueTracker.cpp
@@ -42,7 +42,7 @@ void SSAValueTracker::operator()(VariableDeclaration const& _varDecl)
 			setValue(var.name, nullptr);
 }
 
-void SSAValueTracker::setValue(string const& _name, Expression const* _value)
+void SSAValueTracker::setValue(YulString _name, Expression const* _value)
 {
 	assertThrow(
 		m_values.count(_name) == 0,
diff --git a/libyul/optimiser/SSAValueTracker.h b/libyul/optimiser/SSAValueTracker.h
index 8c39a98e..d1539c86 100644
--- a/libyul/optimiser/SSAValueTracker.h
+++ b/libyul/optimiser/SSAValueTracker.h
@@ -23,7 +23,6 @@
 
 #include <libyul/optimiser/ASTWalker.h>
 
-#include <string>
 #include <map>
 #include <set>
 
@@ -45,13 +44,13 @@ public:
 	virtual void operator()(VariableDeclaration const& _varDecl) override;
 	virtual void operator()(Assignment const& _assignment) override;
 
-	std::map<std::string, Expression const*> const& values() const { return m_values; }
-	Expression const* value(std::string const& _name) const { return m_values.at(_name); }
+	std::map<YulString, Expression const*> const& values() const { return m_values; }
+	Expression const* value(YulString _name) const { return m_values.at(_name); }
 
 private:
-	void setValue(std::string const& _name, Expression const* _value);
+	void setValue(YulString _name, Expression const* _value);
 
-	std::map<std::string, Expression const*> m_values;
+	std::map<YulString, Expression const*> m_values;
 };
 
 }
diff --git a/libyul/optimiser/Semantics.cpp b/libyul/optimiser/Semantics.cpp
index 33f3af77..3c49016e 100644
--- a/libyul/optimiser/Semantics.cpp
+++ b/libyul/optimiser/Semantics.cpp
@@ -40,7 +40,7 @@ MovableChecker::MovableChecker(Expression const& _expression)
 void MovableChecker::operator()(Identifier const& _identifier)
 {
 	ASTWalker::operator()(_identifier);
-	m_variableReferences.insert(_identifier.name);
+	m_variableReferences.emplace(_identifier.name);
 }
 
 void MovableChecker::operator()(FunctionalInstruction const& _instr)
diff --git a/libyul/optimiser/Semantics.h b/libyul/optimiser/Semantics.h
index 1caa12fb..620a91cb 100644
--- a/libyul/optimiser/Semantics.h
+++ b/libyul/optimiser/Semantics.h
@@ -22,8 +22,6 @@
 
 #include <libyul/optimiser/ASTWalker.h>
 
-#include <string>
-#include <map>
 #include <set>
 
 namespace dev
@@ -49,11 +47,11 @@ public:
 	using ASTWalker::visit;
 
 	bool movable() const { return m_movable; }
-	std::set<std::string> const& referencedVariables() const { return m_variableReferences; }
+	std::set<YulString> const& referencedVariables() const { return m_variableReferences; }
 
 private:
 	/// Which variables the current expression references.
-	std::set<std::string> m_variableReferences;
+	std::set<YulString> m_variableReferences;
 	/// Is the current expression movable or not.
 	bool m_movable = true;
 };
diff --git a/libyul/optimiser/SimplificationRules.cpp b/libyul/optimiser/SimplificationRules.cpp
index 8e94fe4d..5721042f 100644
--- a/libyul/optimiser/SimplificationRules.cpp
+++ b/libyul/optimiser/SimplificationRules.cpp
@@ -36,7 +36,7 @@ using namespace dev::yul;
 
 SimplificationRule<Pattern> const* SimplificationRules::findFirstMatch(
 	Expression const& _expr,
-	map<string, Expression const*> const& _ssaValues
+	map<YulString, Expression const*> const& _ssaValues
 )
 {
 	if (_expr.type() != typeid(FunctionalInstruction))
@@ -104,7 +104,7 @@ void Pattern::setMatchGroup(unsigned _group, map<unsigned, Expression const*>& _
 	m_matchGroups = &_matchGroups;
 }
 
-bool Pattern::matches(Expression const& _expr, map<string, Expression const*> const& _ssaValues) const
+bool Pattern::matches(Expression const& _expr, map<YulString, Expression const*> const& _ssaValues) const
 {
 	Expression const* expr = &_expr;
 
@@ -112,7 +112,7 @@ bool Pattern::matches(Expression const& _expr, map<string, Expression const*> co
 	// Do not do it for "Any" because we can check identity better for variables.
 	if (m_kind != PatternKind::Any && _expr.type() == typeid(Identifier))
 	{
-		string const& varName = boost::get<Identifier>(_expr).name;
+		YulString varName = boost::get<Identifier>(_expr).name;
 		if (_ssaValues.count(varName))
 			expr = _ssaValues.at(varName);
 	}
@@ -125,7 +125,7 @@ bool Pattern::matches(Expression const& _expr, map<string, Expression const*> co
 		Literal const& literal = boost::get<Literal>(*expr);
 		if (literal.kind != assembly::LiteralKind::Number)
 			return false;
-		if (m_data && *m_data != u256(literal.value))
+		if (m_data && *m_data != u256(literal.value.str()))
 			return false;
 		assertThrow(m_arguments.empty(), OptimizerException, "");
 	}
@@ -193,7 +193,7 @@ Expression Pattern::toExpression(SourceLocation const& _location) const
 	if (m_kind == PatternKind::Constant)
 	{
 		assertThrow(m_data, OptimizerException, "No match group and no constant value given.");
-		return Literal{_location, assembly::LiteralKind::Number, formatNumber(*m_data), ""};
+		return Literal{_location, assembly::LiteralKind::Number, YulString{formatNumber(*m_data)}, {}};
 	}
 	else if (m_kind == PatternKind::Operation)
 	{
@@ -209,8 +209,8 @@ u256 Pattern::d() const
 {
 	Literal const& literal = boost::get<Literal>(matchGroupValue());
 	assertThrow(literal.kind == assembly::LiteralKind::Number, OptimizerException, "");
-	assertThrow(isValidDecimal(literal.value) || isValidHex(literal.value), OptimizerException, "");
-	return u256(literal.value);
+	assertThrow(isValidDecimal(literal.value.str()) || isValidHex(literal.value.str()), OptimizerException, "");
+	return u256(literal.value.str());
 }
 
 Expression const& Pattern::matchGroupValue() const
diff --git a/libyul/optimiser/SimplificationRules.h b/libyul/optimiser/SimplificationRules.h
index 82ae5d22..b608ca91 100644
--- a/libyul/optimiser/SimplificationRules.h
+++ b/libyul/optimiser/SimplificationRules.h
@@ -52,7 +52,7 @@ public:
 	/// @param _ssaValues values of variables that are assigned exactly once.
 	static SimplificationRule<Pattern> const* findFirstMatch(
 		Expression const& _expr,
-		std::map<std::string, Expression const*> const& _ssaValues
+		std::map<YulString, Expression const*> const& _ssaValues
 	);
 
 	/// Checks whether the rulelist is non-empty. This is usually enforced
@@ -96,7 +96,7 @@ public:
 	/// same expression equivalence class.
 	void setMatchGroup(unsigned _group, std::map<unsigned, Expression const*>& _matchGroups);
 	unsigned matchGroup() const { return m_matchGroup; }
-	bool matches(Expression const& _expr, std::map<std::string, Expression const*> const& _ssaValues) const;
+	bool matches(Expression const& _expr, std::map<YulString, Expression const*> const& _ssaValues) const;
 
 	std::vector<Pattern> arguments() const { return m_arguments; }
 
diff --git a/libyul/optimiser/Substitution.cpp b/libyul/optimiser/Substitution.cpp
index 4a000a85..9b3d4c03 100644
--- a/libyul/optimiser/Substitution.cpp
+++ b/libyul/optimiser/Substitution.cpp
@@ -30,7 +30,7 @@ Expression Substitution::translate(Expression const& _expression)
 {
 	if (_expression.type() == typeid(Identifier))
 	{
-		string const& name = boost::get<Identifier>(_expression).name;
+		YulString name = boost::get<Identifier>(_expression).name;
 		if (m_substitutions.count(name))
 			// No recursive substitution
 			return ASTCopier().translate(*m_substitutions.at(name));
diff --git a/libyul/optimiser/Substitution.h b/libyul/optimiser/Substitution.h
index b734cdca..59ee4620 100644
--- a/libyul/optimiser/Substitution.h
+++ b/libyul/optimiser/Substitution.h
@@ -22,9 +22,9 @@
 
 #include <libyul/optimiser/ASTCopier.h>
 
-#include <string>
+#include <libyul/YulString.h>
+
 #include <map>
-#include <set>
 
 namespace dev
 {
@@ -37,13 +37,13 @@ namespace yul
 class Substitution: public ASTCopier
 {
 public:
-	Substitution(std::map<std::string, Expression const*> const& _substitutions):
+	Substitution(std::map<YulString, Expression const*> const& _substitutions):
 		m_substitutions(_substitutions)
 	{}
 	virtual Expression translate(Expression const& _expression) override;
 
 private:
-	std::map<std::string, Expression const*> const& m_substitutions;
+	std::map<YulString, Expression const*> const& m_substitutions;
 };
 
 }
diff --git a/libyul/optimiser/Suite.cpp b/libyul/optimiser/Suite.cpp
index 5b325afd..c7339d2e 100644
--- a/libyul/optimiser/Suite.cpp
+++ b/libyul/optimiser/Suite.cpp
@@ -48,10 +48,10 @@ using namespace dev::yul;
 void OptimiserSuite::run(
 	Block& _ast,
 	solidity::assembly::AsmAnalysisInfo const& _analysisInfo,
-	set<string> const& _externallyUsedIdentifiers
+	set<YulString> const& _externallyUsedIdentifiers
 )
 {
-	set<string> reservedIdentifiers = _externallyUsedIdentifiers;
+	set<YulString> reservedIdentifiers = _externallyUsedIdentifiers;
 
 	Block ast = boost::get<Block>(Disambiguator(_analysisInfo, reservedIdentifiers)(_ast));
 
diff --git a/libyul/optimiser/Suite.h b/libyul/optimiser/Suite.h
index bb6274bd..5b564c56 100644
--- a/libyul/optimiser/Suite.h
+++ b/libyul/optimiser/Suite.h
@@ -21,9 +21,8 @@
 #pragma once
 
 #include <libyul/ASTDataForward.h>
+#include <libyul/YulString.h>
 
-#include <string>
-#include <map>
 #include <set>
 
 namespace dev
@@ -47,7 +46,8 @@ public:
 	static void run(
 		Block& _ast,
 		solidity::assembly::AsmAnalysisInfo const& _analysisInfo,
-		std::set<std::string> const& _externallyUsedIdentifiers = std::set<std::string>()
+
+		std::set<YulString> const& _externallyUsedIdentifiers = {}
 	);
 };
 
diff --git a/libyul/optimiser/SyntacticalEquality.cpp b/libyul/optimiser/SyntacticalEquality.cpp
index f22b5c31..66912383 100644
--- a/libyul/optimiser/SyntacticalEquality.cpp
+++ b/libyul/optimiser/SyntacticalEquality.cpp
@@ -34,6 +34,7 @@ bool SyntacticalEqualityChecker::equal(Expression const& _e1, Expression const&
 {
 	if (_e1.type() != _e2.type())
 		return false;
+	// TODO This somehow calls strcmp - WHERE?
 
 	// TODO This should be replaced by some kind of AST walker as soon as it gets
 	// more complex.
diff --git a/libyul/optimiser/UnusedPruner.cpp b/libyul/optimiser/UnusedPruner.cpp
index 37a74553..a7b32873 100644
--- a/libyul/optimiser/UnusedPruner.cpp
+++ b/libyul/optimiser/UnusedPruner.cpp
@@ -33,7 +33,7 @@ using namespace std;
 using namespace dev;
 using namespace dev::yul;
 
-UnusedPruner::UnusedPruner(Block& _ast, set<string> const& _externallyUsedFunctions)
+UnusedPruner::UnusedPruner(Block& _ast, set<YulString> const& _externallyUsedFunctions)
 {
 	ReferencesCounter counter;
 	counter(_ast);
@@ -91,7 +91,7 @@ void UnusedPruner::operator()(Block& _block)
 	ASTModifier::operator()(_block);
 }
 
-void UnusedPruner::runUntilStabilised(Block& _ast, set<string> const& _externallyUsedFunctions)
+void UnusedPruner::runUntilStabilised(Block& _ast, set<YulString> const& _externallyUsedFunctions)
 {
 	while (true)
 	{
@@ -102,12 +102,12 @@ void UnusedPruner::runUntilStabilised(Block& _ast, set<string> const& _externall
 	}
 }
 
-bool UnusedPruner::used(string const& _name) const
+bool UnusedPruner::used(YulString _name) const
 {
 	return m_references.count(_name) && m_references.at(_name) > 0;
 }
 
-void UnusedPruner::subtractReferences(map<string, size_t> const& _subtrahend)
+void UnusedPruner::subtractReferences(map<YulString, size_t> const& _subtrahend)
 {
 	for (auto const& ref: _subtrahend)
 	{
diff --git a/libyul/optimiser/UnusedPruner.h b/libyul/optimiser/UnusedPruner.h
index 30617ff3..2dd74940 100644
--- a/libyul/optimiser/UnusedPruner.h
+++ b/libyul/optimiser/UnusedPruner.h
@@ -21,8 +21,8 @@
 #pragma once
 
 #include <libyul/optimiser/ASTWalker.h>
+#include <libyul/YulString.h>
 
-#include <string>
 #include <map>
 #include <set>
 
@@ -44,7 +44,7 @@ namespace yul
 class UnusedPruner: public ASTModifier
 {
 public:
-	explicit UnusedPruner(Block& _ast, std::set<std::string> const& _externallyUsedFunctions = std::set<std::string>());
+	explicit UnusedPruner(Block& _ast, std::set<YulString> const& _externallyUsedFunctions = {});
 
 	using ASTModifier::operator();
 	virtual void operator()(Block& _block) override;
@@ -53,14 +53,14 @@ public:
 	bool shouldRunAgain() const { return m_shouldRunAgain; }
 
 	// Run the pruner until the code does not change anymore.
-	static void runUntilStabilised(Block& _ast, std::set<std::string> const& _externallyUsedFunctions = std::set<std::string>());
+	static void runUntilStabilised(Block& _ast, std::set<YulString> const& _externallyUsedFunctions = {});
 
 private:
-	bool used(std::string const& _name) const;
-	void subtractReferences(std::map<std::string, size_t> const& _subtrahend);
+	bool used(YulString _name) const;
+	void subtractReferences(std::map<YulString, size_t> const& _subtrahend);
 
 	bool m_shouldRunAgain = false;
-	std::map<std::string, size_t> m_references;
+	std::map<YulString, size_t> m_references;
 };
 
 }
diff --git a/libyul/optimiser/VarDeclPropagator.cpp b/libyul/optimiser/VarDeclPropagator.cpp
index 39337b3d..537b7020 100644
--- a/libyul/optimiser/VarDeclPropagator.cpp
+++ b/libyul/optimiser/VarDeclPropagator.cpp
@@ -31,8 +31,8 @@ using dev::solidity::assembly::TypedNameList;
 
 void VarDeclPropagator::operator()(Block& _block)
 {
-	map<string, TypedName> outerEmptyVarDecls;
-	map<string, TypedName> outerLazyInitializedVarDecls;
+	map<YulString, TypedName> outerEmptyVarDecls;
+	map<YulString, TypedName> outerLazyInitializedVarDecls;
 	swap(m_emptyVarDecls, outerEmptyVarDecls);
 	swap(m_lazyInitializedVarDecls, outerLazyInitializedVarDecls);
 
diff --git a/libyul/optimiser/VarDeclPropagator.h b/libyul/optimiser/VarDeclPropagator.h
index 8cba8649..4522d23a 100644
--- a/libyul/optimiser/VarDeclPropagator.h
+++ b/libyul/optimiser/VarDeclPropagator.h
@@ -53,10 +53,10 @@ private:
 
 private:
 	/// Holds a list of variables from current Block that have no value assigned yet.
-	std::map<std::string, TypedName> m_emptyVarDecls;
+	std::map<YulString, TypedName> m_emptyVarDecls;
 
 	/// Holds a list variables (and their TypedName) within the current block.
-	std::map<std::string, TypedName> m_lazyInitializedVarDecls;
+	std::map<YulString, TypedName> m_lazyInitializedVarDecls;
 };
 
 }