Scrutinee Constant Folding

This patch introduces new rules to perform constant folding through
case-expressions.

E.g.,
```
case t -# 10# of _ {  ===> case t of _ {
         5#      -> e1              15#     -> e1
         8#      -> e2              18#     -> e2
         DEFAULT -> e               DEFAULT -> e
```

The initial motivation is that it allows "Merge Nested Cases"
optimization to kick in and to further simplify the code
(see Trac #12877).

Currently we recognize the following operations for Word# and Int#: Add,
Sub, Xor, Not and Negate (for Int# only).

Test Plan: validate

Reviewers: simonpj, austin, bgamari

Reviewed By: simonpj, bgamari

Subscribers: thomie

Differential Revision: https://phabricator.haskell.org/D2762

GHC Trac Issues: #12877

3 files changed, 131 insertions, 0 deletions

diff --git a/testsuite/tests/perf/compiler/T12877.hs b/testsuite/tests/perf/compiler/T12877.hs
new file mode 100644
index 0000000000..2fc7d58dd4
--- /dev/null
+++ b/testsuite/tests/perf/compiler/T12877.hs
@@ -0,0 +1,117 @@
+-- This ugly cascading case reduces to:
+--    case x of
+--       0 -> "0"
+--       1 -> "1"
+--       _ -> "n"
+--
+-- but only if GHC's case-folding reduction kicks in.
+
+{-# NOINLINE test #-}
+test :: Word -> String
+test x = case x of
+   0  -> "0"
+   1  -> "1"
+   t  -> case t + 1 of
+      1 -> "0"
+      2 -> "1"
+      t  -> case t + 1 of
+         2 -> "0"
+         3 -> "1"
+         t  -> case t + 1 of
+            3 -> "0"
+            4 -> "1"
+            t  -> case t + 1 of
+               4 -> "0"
+               5 -> "1"
+               t  -> case t + 1 of
+                  5 -> "0"
+                  6 -> "1"
+                  t  -> case t + 1 of
+                     6 -> "0"
+                     7 -> "1"
+                     t  -> case t + 1 of
+                        7 -> "0"
+                        8 -> "1"
+                        t  -> case t + 1 of
+                           8 -> "0"
+                           9 -> "1"
+                           t  -> case t + 1 of
+                              10 -> "0"
+                              11 -> "1"
+                              t  -> case t + 1 of
+                                 11 -> "0"
+                                 12 -> "1"
+                                 t  -> case t + 1 of
+                                    12 -> "0"
+                                    13 -> "1"
+                                    t  -> case t + 1 of
+                                       13 -> "0"
+                                       14 -> "1"
+                                       t  -> case t + 1 of
+                                          14 -> "0"
+                                          15 -> "1"
+                                          t  -> case t + 1 of
+                                             15 -> "0"
+                                             16 -> "1"
+                                             t  -> case t + 1 of
+                                                16 -> "0"
+                                                17 -> "1"
+                                                t  -> case t + 1 of
+                                                   17 -> "0"
+                                                   18 -> "1"
+                                                   t  -> case t + 1 of
+                                                      18 -> "0"
+                                                      19 -> "1"
+                                                      t  -> case t + 1 of
+                                                         19 -> "0"
+                                                         20 -> "1"
+                                                         t  -> case t + 1 of
+                                                            20 -> "0"
+                                                            21 -> "1"
+                                                            t  -> case t + 1 of
+                                                               21 -> "0"
+                                                               22 -> "1"
+                                                               t  -> case t + 1 of
+                                                                  22 -> "0"
+                                                                  23 -> "1"
+                                                                  t  -> case t + 1 of
+                                                                     23 -> "0"
+                                                                     24 -> "1"
+                                                                     t  -> case t + 1 of
+                                                                        24 -> "0"
+                                                                        25 -> "1"
+                                                                        t  -> case t + 1 of
+                                                                           25 -> "0"
+                                                                           26 -> "1"
+                                                                           t  -> case t + 1 of
+                                                                              26 -> "0"
+                                                                              27 -> "1"
+                                                                              t  -> case t + 1 of
+                                                                                 27 -> "0"
+                                                                                 28 -> "1"
+                                                                                 t  -> case t + 1 of
+                                                                                    28 -> "0"
+                                                                                    29 -> "1"
+                                                                                    t  -> case t + 1 of
+                                                                                       29 -> "0"
+                                                                                       30 -> "1"
+                                                                                       t  -> case t + 1 of
+                                                                                          30 -> "0"
+                                                                                          31 -> "1"
+                                                                                          t  -> case t + 1 of
+                                                                                             31 -> "0"
+                                                                                             32 -> "1"
+                                                                                             t  -> case t + 1 of
+                                                                                                32 -> "0"
+                                                                                                33 -> "1"
+                                                                                                t  -> case t + 1 of
+                                                                                                   33 -> "0"
+                                                                                                   34 -> "1"
+                                                                                                   t  -> case t + 1 of
+                                                                                                      34 -> "0"
+                                                                                                      35 -> "1"
+                                                                                                      _  -> "n"
+
+main :: IO ()
+main = do
+   putStrLn [last (concat (fmap test [0..12345678]))]
diff --git a/testsuite/tests/perf/compiler/T12877.stdout b/testsuite/tests/perf/compiler/T12877.stdout
new file mode 100644
index 0000000000..8ba3a16384
--- /dev/null
+++ b/testsuite/tests/perf/compiler/T12877.stdout
@@ -0,0 +1 @@
+n
diff --git a/testsuite/tests/perf/compiler/all.T b/testsuite/tests/perf/compiler/all.T
index 0ccde15106..38cbdd0311 100644
--- a/testsuite/tests/perf/compiler/all.T
+++ b/testsuite/tests/perf/compiler/all.T
@@ -895,3 +895,16 @@ test('T12234',
      compile,
      [''])
 
+test('T12877',
+     [ stats_num_field('bytes allocated',
+          [(wordsize(64), 197582248, 5),
+          # initial:      197582248 (Linux)
+          ])
+     , compiler_stats_num_field('bytes allocated',
+          [(wordsize(64), 135979000, 5),
+          # initial:      135979000 (Linux)
+          ]),
+     ],
+     compile_and_run,
+     ['-O2'])
+