Merge pull request #5641 from ethereum/supportUnassigned

[Yul] Support unassigned variables in the SSA value tracker and the data flow analyzer.

10 files changed, 65 insertions, 13 deletions

diff --git a/libyul/optimiser/DataFlowAnalyzer.cpp b/libyul/optimiser/DataFlowAnalyzer.cpp
index 64c67b38..7bff2c89 100644
--- a/libyul/optimiser/DataFlowAnalyzer.cpp
+++ b/libyul/optimiser/DataFlowAnalyzer.cpp
@@ -136,17 +136,22 @@ void DataFlowAnalyzer::operator()(Block& _block)
 
 void DataFlowAnalyzer::handleAssignment(set<YulString> const& _variables, Expression* _value)
 {
+	static Expression const zero{Literal{{}, LiteralKind::Number, YulString{"0"}, {}}};
 	clearValues(_variables);
 
 	MovableChecker movableChecker;
 	if (_value)
 		movableChecker.visit(*_value);
-	if (_variables.size() == 1)
+	else
+		for (auto const& var: _variables)
+			m_value[var] = &zero;
+
+	if (_value && _variables.size() == 1)
 	{
 		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))
+		if (movableChecker.movable() && !movableChecker.referencedVariables().count(name))
 			m_value[name] = _value;
 	}
 
diff --git a/libyul/optimiser/DataFlowAnalyzer.h b/libyul/optimiser/DataFlowAnalyzer.h
index cd134d48..4f12ff6a 100644
--- a/libyul/optimiser/DataFlowAnalyzer.h
+++ b/libyul/optimiser/DataFlowAnalyzer.h
@@ -36,6 +36,8 @@ namespace yul
  * Tracks assignments and is used as base class for both Rematerialiser and
  * Common Subexpression Eliminator.
  *
+ * A special zero constant expression is used for the default value of variables.
+ *
  * Prerequisite: Disambiguator
  */
 class DataFlowAnalyzer: public ASTModifier
diff --git a/libyul/optimiser/SSAValueTracker.cpp b/libyul/optimiser/SSAValueTracker.cpp
index ef96c379..a0e44b2b 100644
--- a/libyul/optimiser/SSAValueTracker.cpp
+++ b/libyul/optimiser/SSAValueTracker.cpp
@@ -35,11 +35,12 @@ void SSAValueTracker::operator()(Assignment const& _assignment)
 
 void SSAValueTracker::operator()(VariableDeclaration const& _varDecl)
 {
-	if (_varDecl.variables.size() == 1)
-		setValue(_varDecl.variables.front().name, _varDecl.value.get());
-	else if (!_varDecl.value)
+	static Expression const zero{Literal{{}, LiteralKind::Number, YulString{"0"}, {}}};
+	if (!_varDecl.value)
 		for (auto const& var: _varDecl.variables)
-			setValue(var.name, nullptr);
+			setValue(var.name, &zero);
+	else if (_varDecl.variables.size() == 1)
+		setValue(_varDecl.variables.front().name, _varDecl.value.get());
 }
 
 void SSAValueTracker::setValue(YulString _name, Expression const* _value)
diff --git a/libyul/optimiser/SSAValueTracker.h b/libyul/optimiser/SSAValueTracker.h
index efec2200..0a6cde80 100644
--- a/libyul/optimiser/SSAValueTracker.h
+++ b/libyul/optimiser/SSAValueTracker.h
@@ -33,7 +33,7 @@ namespace yul
  * Class that walks the AST and stores the initial value of each variable
  * that is never assigned to.
  *
- * Default value is represented as nullptr.
+ * A special zero constant expression is used for the default value of variables.
  *
  * Prerequisite: Disambiguator
  */
diff --git a/test/libyul/yulOptimizerTests/commonSubexpressionEliminator/unassigned_variables.yul b/test/libyul/yulOptimizerTests/commonSubexpressionEliminator/unassigned_variables.yul
new file mode 100644
index 00000000..a790ca65
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/commonSubexpressionEliminator/unassigned_variables.yul
@@ -0,0 +1,14 @@
+{
+    // This does not replace b by a because there is no
+    // explicit assignment, even though both hold the same value.
+    let a
+    let b
+    mstore(sub(a, b), 7)
+}
+// ----
+// commonSubexpressionEliminator
+// {
+//     let a
+//     let b
+//     mstore(sub(a, b), 7)
+// }
diff --git a/test/libyul/yulOptimizerTests/expressionSimplifier/unassigend_vars_multi.yul b/test/libyul/yulOptimizerTests/expressionSimplifier/unassigend_vars_multi.yul
index 8c1ad789..f260db0b 100644
--- a/test/libyul/yulOptimizerTests/expressionSimplifier/unassigend_vars_multi.yul
+++ b/test/libyul/yulOptimizerTests/expressionSimplifier/unassigend_vars_multi.yul
@@ -1,5 +1,4 @@
-// c & d can't be optimized as expression simplifier doesn't handle default
-// values yet
+// Unassigned variables are assumed to be zero.
 {
 	let c, d
 	let y := add(d, add(c, 7))
@@ -8,5 +7,5 @@
 // expressionSimplifier
 // {
 //     let c, d
-//     let y := add(add(d, c), 7)
+//     let y := 7
 // }
diff --git a/test/libyul/yulOptimizerTests/expressionSimplifier/unassigned_vars.yul b/test/libyul/yulOptimizerTests/expressionSimplifier/unassigned_vars.yul
index 87391b8c..7b1430f3 100644
--- a/test/libyul/yulOptimizerTests/expressionSimplifier/unassigned_vars.yul
+++ b/test/libyul/yulOptimizerTests/expressionSimplifier/unassigned_vars.yul
@@ -1,5 +1,4 @@
-// c & d can't be optimized as expression simplifier doesn't handle default
-// values yet
+// Unassigned variables are assumed to be zero.
 {
 	let c
 	let d
@@ -10,5 +9,5 @@
 // {
 //     let c
 //     let d
-//     let y := add(add(d, c), 7)
+//     let y := 7
 // }
diff --git a/test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul b/test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul
index 0972ac56..ec44dafb 100644
--- a/test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul
+++ b/test/libyul/yulOptimizerTests/fullInliner/large_function_multi_use.yul
@@ -13,6 +13,9 @@
     let r := f(a)
     // This should be inlined because it is a constant
     let t := f(a2)
+    let a3
+    // This should be inlined because it is a constant as well (zero)
+    let s := f(a3)
 }
 // ----
 // fullInliner
@@ -30,6 +33,16 @@
 //         let f_y := add(f_a, f_x)
 //         sstore(f_y, 10)
 //         let t := f_b
+//         let a3
+//         let f_a_5 := a3
+//         let f_b_6
+//         let f_x_7 := mload(f_a_5)
+//         f_b_6 := sload(f_x_7)
+//         let f_c_8 := 3
+//         mstore(mul(f_a_5, f_b_6), mload(f_x_7))
+//         let f_y_11 := add(f_a_5, f_x_7)
+//         sstore(f_y_11, 10)
+//         let s := f_b_6
 //     }
 //     function f(a) -> b
 //     {
diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/if_multi_unassigned_condition.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/if_multi_unassigned_condition.yul
new file mode 100644
index 00000000..0ece5dbd
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/structuralSimplifier/if_multi_unassigned_condition.yul
@@ -0,0 +1,10 @@
+{
+    let x, y
+    if x { mstore(0, 0) }
+    if y { mstore(0, 0) }
+}
+// ----
+// structuralSimplifier
+// {
+//     let x, y
+// }
diff --git a/test/libyul/yulOptimizerTests/structuralSimplifier/if_unassigned_condition.yul b/test/libyul/yulOptimizerTests/structuralSimplifier/if_unassigned_condition.yul
new file mode 100644
index 00000000..a327a882
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/structuralSimplifier/if_unassigned_condition.yul
@@ -0,0 +1,9 @@
+{
+    let x
+    if x { mstore(0, 0) }
+}
+// ----
+// structuralSimplifier
+// {
+//     let x
+// }