Compiler.Opts.CSE

(source)

This module provides a simple common subexpression elimination (CSE)
algorithm. The main goal right now is to move duplicate
expressions introduced during autosearch (which includes
interface resolution) to the top level.

As such, the functionality provided by this module should
be considered a form of whole program optimization.
To keep things simple, it operates only on closed terms right
now, which are - in case of several occurences - introduced
as new zero-argument toplevel functions.

The procedure is very simple: In an analysis step, we
iterate over all toplevel definitions once, trying to
convert every subexpression to a closed one (no free
variables). Closed terms are then stored in a `SortedMap`
together with their size and count. In order to only use
linear space w.r.t. term size, we start this analysis at the
leaves and substitute closed terms with the machine generated
names before analyzing parent terms.

In a second step, we compare the count of each machine
generated name with the count of its parent expression.
If they are the same, the name is dropped and replaces with
a CSE optimized version of the original expression, otherwise
the name is kept and a new zero argumet function of the
given name is added to the toplevel, thus eliminating the
duplicate expressions.

Definitions

UsageMap : Type

  Maping from a pairing of closed terms together with
  their size (for efficiency) to the number of
  occurences in toplevel definitions and flag for
  whether it was encountered in delayed subexpression.

Visibility: public export

data Count : Type

  Number of appearances of a closed expression.
  
   `Once` : The expression occurs exactly once.
   `Many` : The expression occurs more than once.
   `C n`  : The expression has been counted `n` times
            but we will have to compare this value
            with the number of occurences of its parent
            expression to decide whether it occured
            only once or several times.

Totality: total
Visibility: public export
Constructors:

Once : Count
Many : Count
C : Integer -> Count

Hint:

Show Count

ReplaceMap : Type

  After common subexpression analysis we get a mapping
  from `Name`s to the closed expressions they replace.
  We use this mapping for substituting the names back
  to the corresponding expressions, if the expression
  appears only in one place or is a subexpression of
  some delayed expression.

Visibility: public export

analyze : Ref Sts St => CExp ns -> Core (Integer, CExp ns)

Visibility: export

cse : Ref Ctxt Defs => List Name -> CExp ns -> Core (List (Name, (FC, CDef)), CExp ns)

  Runs the CSE alorithm on all provided names and
  the given main expression.

Visibility: export