Merge pull request #2206 from ethereum/fixoptimizer

Constant optimizer fix

5 files changed, 87 insertions, 25 deletions

diff --git a/Changelog.md b/Changelog.md
index 00400e26..f4b1e20d 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -20,6 +20,7 @@ Bugfixes:
    and source mappings.
  * Gas Estimator: Reflect the most recent fee schedule.
  * Type system: Contract inheriting from base with unimplemented constructor should be abstract.
+ * Optimizer: Number representation bug in the constant optimizer fixed.
 
 ### 0.4.10 (2017-03-15)
 
diff --git a/docs/bugs.json b/docs/bugs.json
index 2a8d167a..78fcf06b 100644
--- a/docs/bugs.json
+++ b/docs/bugs.json
@@ -1,5 +1,16 @@
 [
     {
+        "name": "ConstantOptimizerSubtraction",
+        "summary": "In some situations, the optimizer replaces certain numbers in the code with routines that compute different numbers.",
+        "description": "The optimizer tries to represent any number in the bytecode by routines that compute them with less gas. For some special numbers, an incorrect routine is generated. This could allow an attacker to e.g. trick victims about a specific amount of ether, or function calls to call different functions (or none at all).",
+        "link": "https://blog.ethereum.org/2017/04/24/solidity-optimizer-bug/",
+        "fixed": "0.4.11",
+        "severity": "low",
+        "conditions": {
+            "optimizer": true
+        }
+    },
+    {
         "name": "IdentityPrecompileReturnIgnored",
         "summary": "Failure of the identity precompile was ignored.",
         "description": "Calls to the identity contract, which is used for copying memory, ignored its return value. On the public chain, calls to the identity precompile can be made in a way that they never fail, but this might be different on private chains.",
diff --git a/docs/bugs_by_version.json b/docs/bugs_by_version.json
index 64015d4a..7fbca437 100644
--- a/docs/bugs_by_version.json
+++ b/docs/bugs_by_version.json
@@ -1,6 +1,7 @@
 {
     "0.1.0": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "OptimizerStaleKnowledgeAboutSHA3", 
             "SendFailsForZeroEther", 
@@ -14,6 +15,7 @@
     }, 
     "0.1.1": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "OptimizerStaleKnowledgeAboutSHA3", 
             "SendFailsForZeroEther", 
@@ -27,6 +29,7 @@
     }, 
     "0.1.2": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "OptimizerStaleKnowledgeAboutSHA3", 
             "SendFailsForZeroEther", 
@@ -40,6 +43,7 @@
     }, 
     "0.1.3": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "OptimizerStaleKnowledgeAboutSHA3", 
             "SendFailsForZeroEther", 
@@ -53,6 +57,7 @@
     }, 
     "0.1.4": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "OptimizerStaleKnowledgeAboutSHA3", 
             "SendFailsForZeroEther", 
@@ -66,6 +71,7 @@
     }, 
     "0.1.5": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "OptimizerStaleKnowledgeAboutSHA3", 
             "SendFailsForZeroEther", 
@@ -79,6 +85,7 @@
     }, 
     "0.1.6": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -93,6 +100,7 @@
     }, 
     "0.1.7": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -107,6 +115,7 @@
     }, 
     "0.2.0": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -121,6 +130,7 @@
     }, 
     "0.2.1": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -135,6 +145,7 @@
     }, 
     "0.2.2": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -149,6 +160,7 @@
     }, 
     "0.3.0": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -162,6 +174,7 @@
     }, 
     "0.3.1": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -174,6 +187,7 @@
     }, 
     "0.3.2": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -186,6 +200,7 @@
     }, 
     "0.3.3": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -197,6 +212,7 @@
     }, 
     "0.3.4": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -208,6 +224,7 @@
     }, 
     "0.3.5": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -219,6 +236,7 @@
     }, 
     "0.3.6": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -228,6 +246,7 @@
     }, 
     "0.4.0": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -237,6 +256,7 @@
     }, 
     "0.4.1": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3", 
@@ -245,11 +265,14 @@
         "released": "2016-09-09"
     }, 
     "0.4.10": {
-        "bugs": [], 
+        "bugs": [
+            "ConstantOptimizerSubtraction"
+        ], 
         "released": "2017-03-15"
     }, 
     "0.4.2": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage", 
             "OptimizerStaleKnowledgeAboutSHA3"
@@ -258,6 +281,7 @@
     }, 
     "0.4.3": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "HighOrderByteCleanStorage"
         ], 
@@ -265,12 +289,14 @@
     }, 
     "0.4.4": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored"
         ], 
         "released": "2016-10-31"
     }, 
     "0.4.5": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored", 
             "OptimizerStateKnowledgeNotResetForJumpdest"
         ], 
@@ -278,20 +304,27 @@
     }, 
     "0.4.6": {
         "bugs": [
+            "ConstantOptimizerSubtraction", 
             "IdentityPrecompileReturnIgnored"
         ], 
         "released": "2016-11-22"
     }, 
     "0.4.7": {
-        "bugs": [], 
+        "bugs": [
+            "ConstantOptimizerSubtraction"
+        ], 
         "released": "2016-12-15"
     }, 
     "0.4.8": {
-        "bugs": [], 
+        "bugs": [
+            "ConstantOptimizerSubtraction"
+        ], 
         "released": "2017-01-13"
     }, 
     "0.4.9": {
-        "bugs": [], 
+        "bugs": [
+            "ConstantOptimizerSubtraction"
+        ], 
         "released": "2017-01-31"
     }
 }
\ No newline at end of file
diff --git a/libevmasm/ConstantOptimiser.cpp b/libevmasm/ConstantOptimiser.cpp
index d2ed4faf..0c093ebf 100644
--- a/libevmasm/ConstantOptimiser.cpp
+++ b/libevmasm/ConstantOptimiser.cpp
@@ -203,8 +203,13 @@ AssemblyItems ComputeMethod::findRepresentation(u256 const& _value)
 			u256 powerOfTwo = u256(1) << bits;
 			u256 upperPart = _value >> bits;
 			bigint lowerPart = _value & (powerOfTwo - 1);
-			if (abs(powerOfTwo - lowerPart) < lowerPart)
+			if ((powerOfTwo - lowerPart) < lowerPart)
+			{
 				lowerPart = lowerPart - powerOfTwo; // make it negative
+				upperPart++;
+			}
+			if (upperPart == 0)
+				continue;
 			if (abs(lowerPart) >= (powerOfTwo >> 8))
 				continue;
 
@@ -212,7 +217,7 @@ AssemblyItems ComputeMethod::findRepresentation(u256 const& _value)
 			if (lowerPart != 0)
 				newRoutine += findRepresentation(u256(abs(lowerPart)));
 			newRoutine += AssemblyItems{u256(bits), u256(2), Instruction::EXP};
-			if (upperPart != 1 && upperPart != 0)
+			if (upperPart != 1)
 				newRoutine += findRepresentation(upperPart) + AssemblyItems{Instruction::MUL};
 			if (lowerPart > 0)
 				newRoutine += AssemblyItems{Instruction::ADD};
diff --git a/test/libsolidity/SolidityOptimizer.cpp b/test/libsolidity/SolidityOptimizer.cpp
index bcf6cd49..d705e3c8 100644
--- a/test/libsolidity/SolidityOptimizer.cpp
+++ b/test/libsolidity/SolidityOptimizer.cpp
@@ -74,16 +74,17 @@ public:
 	void compileBothVersions(
 		std::string const& _sourceCode,
 		u256 const& _value = 0,
-		std::string const& _contractName = ""
+		std::string const& _contractName = "",
+		unsigned const _optimizeRuns = 200
 	)
 	{
-		bytes nonOptimizedBytecode = compileAndRunWithOptimizer(_sourceCode, _value, _contractName, false);
+		bytes nonOptimizedBytecode = compileAndRunWithOptimizer(_sourceCode, _value, _contractName, false, _optimizeRuns);
 		m_nonOptimizedContract = m_contractAddress;
-		bytes optimizedBytecode = compileAndRunWithOptimizer(_sourceCode, _value, _contractName, true);
+		bytes optimizedBytecode = compileAndRunWithOptimizer(_sourceCode, _value, _contractName, true, _optimizeRuns);
 		size_t nonOptimizedSize = numInstructions(nonOptimizedBytecode);
 		size_t optimizedSize = numInstructions(optimizedBytecode);
 		BOOST_CHECK_MESSAGE(
-			optimizedSize < nonOptimizedSize,
+			_optimizeRuns < 50 || optimizedSize < nonOptimizedSize,
 			string("Optimizer did not reduce bytecode size. Non-optimized size: ") +
 			std::to_string(nonOptimizedSize) + " - optimized size: " +
 			std::to_string(optimizedSize)
@@ -1191,31 +1192,42 @@ BOOST_AUTO_TEST_CASE(clear_unreachable_code)
 BOOST_AUTO_TEST_CASE(computing_constants)
 {
 	char const* sourceCode = R"(
-		contract c {
-			uint a;
-			uint b;
-			uint c;
-			function set() returns (uint a, uint b, uint c) {
-				a = 0x77abc0000000000000000000000000000000000000000000000000000000001;
-				b = 0x817416927846239487123469187231298734162934871263941234127518276;
+		contract C {
+			uint m_a;
+			uint m_b;
+			uint m_c;
+			uint m_d;
+			function C() {
+				set();
+			}
+			function set() returns (uint) {
+				m_a = 0x77abc0000000000000000000000000000000000000000000000000000000001;
+				m_b = 0x817416927846239487123469187231298734162934871263941234127518276;
 				g();
+				return 1;
 			}
 			function g() {
-				b = 0x817416927846239487123469187231298734162934871263941234127518276;
-				c = 0x817416927846239487123469187231298734162934871263941234127518276;
+				m_b = 0x817416927846239487123469187231298734162934871263941234127518276;
+				m_c = 0x817416927846239487123469187231298734162934871263941234127518276;
+				h();
+			}
+			function h() {
+				m_d = 0xff05694900000000000000000000000000000000000000000000000000000000;
 			}
-			function get() returns (uint ra, uint rb, uint rc) {
-				ra = a;
-				rb = b;
-				rc = c ;
+			function get() returns (uint ra, uint rb, uint rc, uint rd) {
+				ra = m_a;
+				rb = m_b;
+				rc = m_c;
+				rd = m_d;
 			}
 		}
 	)";
-	compileBothVersions(sourceCode);
+	compileBothVersions(sourceCode, 0, "C", 1);
+	compareVersions("get()");
 	compareVersions("set()");
 	compareVersions("get()");
 
-	bytes optimizedBytecode = compileAndRunWithOptimizer(sourceCode, 0, "c", true, 1);
+	bytes optimizedBytecode = compileAndRunWithOptimizer(sourceCode, 0, "C", true, 1);
 	bytes complicatedConstant = toBigEndian(u256("0x817416927846239487123469187231298734162934871263941234127518276"));
 	unsigned occurrences = 0;
 	for (auto iter = optimizedBytecode.cbegin(); iter < optimizedBytecode.cend(); ++occurrences)