Optimize dup drop

[EmilySillars]

Greg Next Steps

• Use DContoFunc.hs as reference for how to use everywhereM
• Implement the following two functions, then call them using everywhereM:
  • inExpr: Description: returns whether binder is present in IR sub tree. Type: IR.Expr -> PresentFn IR.Expr where PresentFn is a writer monad containing a boolean.
  • tryElimsAndTrans: Tries to perform each of the eliminiations/transformations on each IR node. Specifically, this function tries to perform swapAppAndDrop, moveDropInsideLet, fusePair, and eliminateConsumptionPat on each IR node. Whenever an eliminiation or transformation is successfully performed, record which elim/trans performed. Type: IR.Expr -> RecordFn IR.Expr Where RecordFn is a writer monad containing a list of strings (or some kind of book keeping structure of your choice)
• document swapAppAndDrop, moveDropInsideLet, fusePair, and eliminateConsumptionPat in a comment on this PR
• add unit tests for swapAppAndDrop, moveDropInsideLet, fusePair, and eliminateConsumptionPat; inside each unit test, include comments describing what the unit test is testing.

[EmilySillars]

Greg Next Steps (Updated!)

@gschare follow up with a comment on this draft PR if you have any questions

I. Implement the following helper functions 1) fusePair :: I.Expr I.Type -> Maybe (I.Expr I.Type) Write a description of this elimination pattern including a small example. 2) eliminateConsumptionPat :: I.Expr I.Type -> Maybe (I.Expr I.Type) Write a description of this elimination pattern including a small example. 3) swapAppAndDrop :: I.Expr I.Type -> Maybe (I.Expr I.Type) Write a description of this transformation including a small example. 4) inExpr :: I.Expr -> I.Binder I.Type -> Bool Description: returns whether binder is present in IR sub tree. 5) moveDropInsideLet :: I.Expr I.Type -> Maybe (I.Expr I.Type) Use the inExpr function to Implement moveDropInsideLet. Write a description of this transformation including a small example.

If you are strapped on time, skip helper funcs #4 and #5.

II. Implement a pass over the IR that tries to apply each elimination or transformation on each node of the AST, and records how many times each elimination or transformation was successfully performed.

• tryElimsAndTrans :: I.Expr I.Type -> DupDropFn (I.Expr I.Type) where DupDropFn is a state monad:

  
  -- | Dup Drop Optimization Environment
  data DupDropCtx = DupDropCtx
  { num_fusePair :: Int
  -- ^ 'num_fusePair' the number of times fusePair was successfully performed.
  , num_eliminateConsumptionPat :: Int
  -- ^ 'num_eliminateConsumptionPat' the number of times eliminateConsumptionPat was successfully performed.
  , num_swapAppAndDrop :: Int
  -- ^ 'num_swapAppAndDrop' the number of times swapAppAndDrop was successfully performed.
  , num_moveDropInsideLet :: Int
  -- ^ 'num_moveDropInsideLet' the number of times moveDropInsideLet was successfully performed.
  }

-- | Dup Drop Monad newtype DupDropFn a = DupDropFn (StateT DuprDropCtx Compiler.Pass a) deriving (Functor) via (StateT DuprDropCtx Compiler.Pass) deriving (Applicative) via (StateT DuprDropCtx Compiler.Pass) deriving (Monad) via (StateT DuprDropCtx Compiler.Pass) deriving (MonadFail) via (StateT DuprDropCtx Compiler.Pass) deriving (MonadError Compiler.Error) via (StateT DuprDropCtx Compiler.Pass) deriving (MonadState DuprDropCtx) via (StateT DuprDropCtx Compiler.Pass)

- Use [DContoFunc.hs](https://github.com/ssm-lang/sslang/blob/main/src/IR/DConToFunc.hs) as reference for how to use everywhereM

**III. Make sure this optimization pass passes all regressions tests and does not cause any memory errors (passes valgrind test, and SSLANG memory management test).** 
- unit tests not needed