optimize linear sums (#904)

6 files changed, 348 insertions, 92 deletions

diff --git a/test/emcc_hello_world.fromasm b/test/emcc_hello_world.fromasm
index b3d40099f..5ac7af9f6 100644
--- a/test/emcc_hello_world.fromasm
+++ b/test/emcc_hello_world.fromasm
@@ -5206,15 +5206,12 @@
                                                     (i32.add
                                                       (i32.add
                                                         (get_local $8)
-                                                        (i32.const 4)
-                                                      )
-                                                      (i32.shl
-                                                        (i32.add
+                                                        (i32.shl
                                                           (get_local $13)
-                                                          (i32.const -1024)
+                                                          (i32.const 2)
                                                         )
-                                                        (i32.const 2)
                                                       )
+                                                      (i32.const -4092)
                                                     )
                                                   )
                                                 )
diff --git a/test/emcc_hello_world.fromasm.imprecise b/test/emcc_hello_world.fromasm.imprecise
index 2e35d2a56..096d105b8 100644
--- a/test/emcc_hello_world.fromasm.imprecise
+++ b/test/emcc_hello_world.fromasm.imprecise
@@ -5143,18 +5143,15 @@
                                                     (i32.add
                                                       (i32.add
                                                         (get_local $8)
-                                                        (i32.const 4)
-                                                      )
-                                                      (i32.shl
-                                                        (i32.add
+                                                        (i32.shl
                                                           (i32.div_s
                                                             (get_local $13)
                                                             (i32.const 9)
                                                           )
-                                                          (i32.const -1024)
+                                                          (i32.const 2)
                                                         )
-                                                        (i32.const 2)
                                                       )
+                                                      (i32.const -4092)
                                                     )
                                                   )
                                                 )
diff --git a/test/passes/optimize-instructions.txt b/test/passes/optimize-instructions.txt
index 14f29a783..a11bd0d66 100644
--- a/test/passes/optimize-instructions.txt
+++ b/test/passes/optimize-instructions.txt
@@ -417,18 +417,12 @@
     )
   )
   (func $load-off-2 (type $3) (param $0 i32) (result i32)
-    (i32.store offset=2
-      (i32.add
-        (i32.const 1)
-        (i32.const 3)
-      )
+    (i32.store
+      (i32.const 6)
       (get_local $0)
     )
-    (i32.store offset=2
-      (i32.add
-        (i32.const 3)
-        (i32.const 1)
-      )
+    (i32.store
+      (i32.const 6)
       (get_local $0)
     )
     (i32.store offset=2
@@ -459,18 +453,12 @@
       )
       (get_local $0)
     )
-    (i32.store offset=2
-      (i32.add
-        (i32.const -15)
-        (i32.const 17)
-      )
+    (i32.store
+      (i32.const 4)
       (get_local $0)
     )
-    (i32.store offset=2
-      (i32.add
-        (i32.const -21)
-        (i32.const 19)
-      )
+    (i32.store
+      (i32.const 0)
       (get_local $0)
     )
     (i32.store
@@ -482,19 +470,13 @@
       (get_local $0)
     )
     (drop
-      (i32.load offset=2
-        (i32.add
-          (i32.const 2)
-          (i32.const 4)
-        )
+      (i32.load
+        (i32.const 8)
       )
     )
     (drop
-      (i32.load offset=2
-        (i32.add
-          (i32.const 4)
-          (i32.const 2)
-        )
+      (i32.load
+        (i32.const 8)
       )
     )
     (drop
@@ -944,4 +926,96 @@
       )
     )
   )
+  (func $linear-sums (type $4) (param $0 i32) (param $1 i32)
+    (drop
+      (i32.add
+        (get_local $1)
+        (i32.shl
+          (get_local $0)
+          (i32.const 4)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.add
+          (get_local $1)
+          (i32.shl
+            (get_local $0)
+            (i32.const 3)
+          )
+        )
+        (i32.const 12)
+      )
+    )
+    (drop
+      (i32.const 4)
+    )
+    (drop
+      (i32.const 18)
+    )
+    (drop
+      (i32.const 6)
+    )
+    (drop
+      (i32.const -4)
+    )
+    (drop
+      (i32.const 2)
+    )
+    (drop
+      (i32.const 1)
+    )
+    (drop
+      (i32.const 26)
+    )
+    (drop
+      (i32.const -20)
+    )
+    (drop
+      (i32.const 22)
+    )
+    (drop
+      (i32.add
+        (i32.shl
+          (i32.const 1)
+          (get_local $0)
+        )
+        (i32.const 14)
+      )
+    )
+    (drop
+      (i32.add
+        (i32.shl
+          (get_local $1)
+          (i32.const 3)
+        )
+        (i32.const -66)
+      )
+    )
+    (drop
+      (i32.const 44)
+    )
+    (drop
+      (i32.add
+        (i32.mul
+          (get_local $0)
+          (i32.const 10)
+        )
+        (i32.const 14)
+      )
+    )
+    (drop
+      (i32.add
+        (i32.mul
+          (get_local $0)
+          (i32.const 2)
+        )
+        (i32.const 34)
+      )
+    )
+    (drop
+      (get_local $0)
+    )
+  )
 )
diff --git a/test/passes/optimize-instructions.wast b/test/passes/optimize-instructions.wast
index 8eec3f3cd..b9bd420da 100644
--- a/test/passes/optimize-instructions.wast
+++ b/test/passes/optimize-instructions.wast
@@ -1014,4 +1014,228 @@
       )
     )
   )
+  (func $linear-sums (param $0 i32) (param $1 i32)
+    (drop
+      (i32.add
+        (i32.add
+          (get_local $1)
+          (i32.const 16)
+        )
+        (i32.shl
+          (i32.add
+            (get_local $0)
+            (i32.const -1) ;; -16, so cancels out!
+          )
+          (i32.const 4)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.add
+          (get_local $1)
+          (i32.const 20)
+        )
+        (i32.shl
+          (i32.add
+            (get_local $0)
+            (i32.const -1) ;; -8, so sum is +12
+          )
+          (i32.const 3)
+        )
+      )
+    )
+    (drop
+      (i32.add ;; simple sum
+        (i32.const 1)
+        (i32.const 3)
+      )
+    )
+    (drop
+      (i32.add ;; nested sum
+        (i32.add
+          (i32.const 1)
+          (i32.const 3)
+        )
+        (i32.add
+          (i32.const 5)
+          (i32.const 9)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.add
+          (i32.const 1)
+          (i32.const 3)
+        )
+        (i32.sub ;; internal sub
+          (i32.const 5)
+          (i32.const 3)
+        )
+      )
+    )
+    (drop
+      (i32.sub ;; external sub
+        (i32.add
+          (i32.const 1)
+          (i32.const 3)
+        )
+        (i32.add
+          (i32.const 5)
+          (i32.const 3)
+        )
+      )
+    )
+    (drop
+      (i32.sub ;; external sub
+        (i32.add
+          (i32.const 1)
+          (i32.const 3)
+        )
+        (i32.sub ;; and also internal sub
+          (i32.const 5)
+          (i32.const 3)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.add
+          (i32.const 1)
+          (i32.const 3)
+        )
+        (i32.sub ;; negating sub
+          (i32.const 0)
+          (i32.const 3)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.sub
+          (i32.const 0)
+          (i32.sub ;; two negating subs
+            (i32.const 0)
+            (i32.add
+              (i32.const 3)
+              (i32.const 20)
+            )
+          )
+        )
+        (i32.add
+          (i32.const 1)
+          (i32.const 2)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.add
+          (i32.const 0)
+          (i32.sub ;; one negating sub
+            (i32.const 0)
+            (i32.add
+              (i32.const 3)
+              (i32.const 20)
+            )
+          )
+        )
+        (i32.add
+          (i32.const 1)
+          (i32.const 2)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.shl ;; shifted value
+          (i32.const 1)
+          (i32.const 3)
+        )
+        (i32.add
+          (i32.const 5)
+          (i32.const 9)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.shl ;; shifted value
+          (i32.const 1)
+          (get_local $0) ;; but not by const
+        )
+        (i32.add
+          (i32.const 5)
+          (i32.const 9)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.shl ;; shifted nested value
+          (i32.sub
+            (get_local $1)
+            (i32.const 10)
+          )
+          (i32.const 3)
+        )
+        (i32.add
+          (i32.const 5)
+          (i32.const 9)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.mul ;; multiplied
+          (i32.const 10)
+          (i32.const 3)
+        )
+        (i32.add
+          (i32.const 5)
+          (i32.const 9)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.mul ;; multiplied by nonconstant - can't recurse
+          (i32.const 10)
+          (get_local $0)
+        )
+        (i32.add
+          (i32.const 5)
+          (i32.const 9)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.mul ;; nested mul
+          (i32.add
+            (i32.const 10)
+            (get_local $0)
+          )
+          (i32.const 2)
+        )
+        (i32.add
+          (i32.const 5)
+          (i32.const 9)
+        )
+      )
+    )
+    (drop
+      (i32.add
+        (i32.add
+          (get_local $0)
+          (i32.const 10) ;; cancelled out with the below
+        )
+        (i32.sub
+          (i32.const -5)
+          (i32.const 5)
+        )
+      )
+    )
+  )
 )
diff --git a/test/unit.fromasm b/test/unit.fromasm
index d2f569684..2a6c60735 100644
--- a/test/unit.fromasm
+++ b/test/unit.fromasm
@@ -279,19 +279,13 @@
       (f32.neg
         (get_local $0)
       )
-      (i32.add
-        (i32.const 8)
-        (i32.const 1)
-      )
+      (i32.const 9)
     )
   )
   (func $cneg (param $0 f32)
     (call_indirect $FUNCSIG$vf
       (get_local $0)
-      (i32.add
-        (i32.const 8)
-        (i32.const 1)
-      )
+      (i32.const 9)
     )
   )
   (func $smallCompare (result i32)
@@ -326,10 +320,7 @@
   (func $cneg_nosemicolon
     (call_indirect $FUNCSIG$vi
       (i32.const 1)
-      (i32.add
-        (i32.const 16)
-        (i32.const 1)
-      )
+      (i32.const 17)
     )
   )
   (func $forLoop
@@ -416,14 +407,8 @@
     (drop
       (call $lb
         (i32.add
-          (i32.add
-            (i32.add
-              (get_local $0)
-              (i32.const 3)
-            )
-            (i32.const 7)
-          )
-          (i32.const 12)
+          (get_local $0)
+          (i32.const 22)
         )
       )
     )
@@ -497,11 +482,8 @@
     (i32.store
       (get_local $0)
       (i32.add
-        (i32.add
-          (get_global $n)
-          (i32.const 136)
-        )
-        (i32.const 8)
+        (get_global $n)
+        (i32.const 144)
       )
     )
     (i32.const 0)
diff --git a/test/unit.fromasm.imprecise b/test/unit.fromasm.imprecise
index 5951d9941..10c1c025c 100644
--- a/test/unit.fromasm.imprecise
+++ b/test/unit.fromasm.imprecise
@@ -247,19 +247,13 @@
       (f32.neg
         (get_local $0)
       )
-      (i32.add
-        (i32.const 8)
-        (i32.const 1)
-      )
+      (i32.const 9)
     )
   )
   (func $cneg (param $0 f32)
     (call_indirect $FUNCSIG$vf
       (get_local $0)
-      (i32.add
-        (i32.const 8)
-        (i32.const 1)
-      )
+      (i32.const 9)
     )
   )
   (func $smallCompare (result i32)
@@ -294,10 +288,7 @@
   (func $cneg_nosemicolon
     (call_indirect $FUNCSIG$vi
       (i32.const 1)
-      (i32.add
-        (i32.const 16)
-        (i32.const 1)
-      )
+      (i32.const 17)
     )
   )
   (func $forLoop
@@ -384,14 +375,8 @@
     (drop
       (call $lb
         (i32.add
-          (i32.add
-            (i32.add
-              (get_local $0)
-              (i32.const 3)
-            )
-            (i32.const 7)
-          )
-          (i32.const 12)
+          (get_local $0)
+          (i32.const 22)
         )
       )
     )
@@ -465,11 +450,8 @@
     (i32.store
       (get_local $0)
       (i32.add
-        (i32.add
-          (get_global $n)
-          (i32.const 136)
-        )
-        (i32.const 8)
+        (get_global $n)
+        (i32.const 144)
       )
     )
     (i32.const 0)