More flexible way to approach unknown stack elements.

3 files changed, 34 insertions, 12 deletions

diff --git a/ExpressionClasses.cpp b/ExpressionClasses.cpp
index 1e60a7fe..8d0785d3 100644
--- a/ExpressionClasses.cpp
+++ b/ExpressionClasses.cpp
@@ -37,6 +37,7 @@ using namespace dev::eth;
 
 bool ExpressionClasses::Expression::operator<(ExpressionClasses::Expression const& _other) const
 {
+	assertThrow(!!item && !!_other.item, OptimizerException, "");
 	auto type = item->type();
 	auto otherType = _other.item->type();
 	return std::tie(type, item->data(), arguments, sequenceNumber) <
@@ -78,6 +79,15 @@ ExpressionClasses::Id ExpressionClasses::find(
 	return exp.id;
 }
 
+ExpressionClasses::Id ExpressionClasses::newId()
+{
+	// Note that we cannot insert it in m_expressions because this requires item to be set.
+	Expression exp;
+	exp.id = m_representatives.size();
+	m_representatives.push_back(exp);
+	return exp.id;
+}
+
 bool ExpressionClasses::knownToBeDifferent(ExpressionClasses::Id _a, ExpressionClasses::Id _b)
 {
 	// Try to simplify "_a - _b" and return true iff the value is a non-zero constant.
@@ -122,10 +132,16 @@ string ExpressionClasses::fullDAGToString(ExpressionClasses::Id _id) const
 {
 	Expression const& expr = representative(_id);
 	stringstream str;
-	str << dec << expr.id << ":" << *expr.item << "(";
-	for (Id arg: expr.arguments)
-		str << fullDAGToString(arg) << ",";
-	str << ")";
+	str << dec << expr.id << ":";
+	if (expr.item)
+	{
+		str << *expr.item << "(";
+		for (Id arg: expr.arguments)
+			str << fullDAGToString(arg) << ",";
+		str << ")";
+	}
+	else
+		str << " UNIQUE";
 	return str.str();
 }
 
@@ -279,7 +295,7 @@ ExpressionClasses::Id ExpressionClasses::tryToSimplify(Expression const& _expr,
 {
 	static Rules rules;
 
-	if (_expr.item->type() != Operation)
+	if (!_expr.item || _expr.item->type() != Operation)
 		return -1;
 
 	for (auto const& rule: rules.rules())
@@ -337,7 +353,7 @@ void Pattern::setMatchGroup(unsigned _group, map<unsigned, Expression const*>& _
 
 bool Pattern::matches(Expression const& _expr, ExpressionClasses const& _classes) const
 {
-	if (!matchesBaseItem(*_expr.item))
+	if (!matchesBaseItem(_expr.item))
 		return false;
 	if (m_matchGroup)
 	{
@@ -387,13 +403,15 @@ string Pattern::toString() const
 	return s.str();
 }
 
-bool Pattern::matchesBaseItem(AssemblyItem const& _item) const
+bool Pattern::matchesBaseItem(AssemblyItem const* _item) const
 {
 	if (m_type == UndefinedItem)
 		return true;
-	if (m_type != _item.type())
+	if (!_item)
+		return false;
+	if (m_type != _item->type())
 		return false;
-	if (m_requireDataMatch && m_data != _item.data())
+	if (m_requireDataMatch && m_data != _item->data())
 		return false;
 	return true;
 }
diff --git a/ExpressionClasses.h b/ExpressionClasses.h
index 2f720f60..5d32c0f7 100644
--- a/ExpressionClasses.h
+++ b/ExpressionClasses.h
@@ -50,7 +50,7 @@ public:
 	struct Expression
 	{
 		Id id;
-		AssemblyItem const* item;
+		AssemblyItem const* item = nullptr;
 		Ids arguments;
 		unsigned sequenceNumber; ///< Storage modification sequence, only used for SLOAD/SSTORE instructions.
 		/// Behaves as if this was a tuple of (item->type(), item->data(), arguments, sequenceNumber).
@@ -68,6 +68,10 @@ public:
 		bool _copyItem = true,
 		unsigned _sequenceNumber = 0
 	);
+	/// @returns a new unique class id which does not and will never have a representative containing
+	/// an AssemblyItem, i.e. its value cannot be generated, instead it has to be assumed to be
+	/// already present.
+	Id newId();
 	/// @returns the canonical representative of an expression class.
 	Expression const& representative(Id _id) const { return m_representatives.at(_id); }
 	/// @returns the number of classes.
@@ -149,7 +153,7 @@ public:
 	std::string toString() const;
 
 private:
-	bool matchesBaseItem(AssemblyItem const& _item) const;
+	bool matchesBaseItem(AssemblyItem const* _item) const;
 	Expression const& matchGroupValue() const;
 
 	AssemblyItemType m_type;
diff --git a/KnownState.cpp b/KnownState.cpp
index 244270fb..e83810d4 100644
--- a/KnownState.cpp
+++ b/KnownState.cpp
@@ -136,7 +136,7 @@ ExpressionClasses::Id KnownState::stackElement(int _stackHeight, SourceLocation
 	if (m_stackElements.count(_stackHeight))
 		return m_stackElements.at(_stackHeight);
 	// Stack element not found (not assigned yet), create new equivalence class.
-	return m_stackElements[_stackHeight] = initialStackElement(_stackHeight, _location);
+	return m_stackElements[_stackHeight] = m_expressionClasses->newId();
 }
 
 ExpressionClasses::Id KnownState::initialStackElement(