Add -foptimal-applicative-do

Summary:
The algorithm for ApplicativeDo rearrangement is based on a heuristic
that runs in O(n^2).  This patch adds the optimal algorithm, which is
O(n^3), selected by a flag (-foptimal-applicative-do).  It finds better
solutions in a small number of cases (about 2% of the cases where
ApplicativeDo makes a difference), but it can be very slow for large do
expressions.  I'm mainly adding it for experimental reasons.

ToDo: user guide docs

Test Plan: validate

Reviewers: simonpj, bgamari, austin, niteria, erikd

Subscribers: thomie

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

1 files changed, 6 insertions, 0 deletions

diff --git a/utils/mkUserGuidePart/Options/Optimizations.hs b/utils/mkUserGuidePart/Options/Optimizations.hs
index 389cd37c68..dd9ffd9ced 100644
--- a/utils/mkUserGuidePart/Options/Optimizations.hs
+++ b/utils/mkUserGuidePart/Options/Optimizations.hs
@@ -216,6 +216,12 @@ optimizationsOptions =
          , flagType = DynamicFlag
          , flagReverse = "-fno-omit-yields"
          }
+  , flag { flagName = "-foptimal-applicative-do"
+         , flagDescription =
+           "Use a slower but better algorithm for ApplicativeDo"
+         , flagType = DynamicFlag
+         , flagReverse = "-fno-optimal-applicative-do"
+         }
   , flag { flagName = "-fpedantic-bottoms"
          , flagDescription =
            "Make GHC be more precise about its treatment of bottom (but see "++