Add a constant-propagation pass

[digikar99]

EDIT: This PR aims to propagate constant literals or other constant objects such as obtained from node-lisp or dict-variables/codegen-syms required to resolve method instances.

Two issues remain for future work:

1. Determining the set of constant objects might require a list of predicates which may be domain-specific. Let's leave that for future work. Implementing it is trivial, but brainstorming what the right way to do it might take some time. (See this thread.)
2. It turns out that while propagating constants, it also becomes possible to update the types of certain nodes. (See this thread.) It's also possible that there are other passes which may make it advantageous to update the node types. In that case, it seems more appropriate to implement node type updation in the traverse pass itself, rather than specifically as part of constant propagation. Thus, updating the traverse functions to update the node types is another branch of future work.

---

Consider the following example:

(in-package :coalton-user)

(coalton-toplevel
  (declare add-df (double-float -> double-float -> double-float))
  (define (add-df x y)
    (lisp double-float (x y) (cl:+ x y)))

  (define (add-df-caller)
    (let ((x 5.0d0))
      (add-df x x))))

Without the constant-propagation pass, (lookup-code 'add-df-caller) returns a node containing a let with a variable binding followed by direct-application:

#s(coalton-impl/codegen/ast:node-let
   :type double-float
   :bindings ((x-4321
               . #s(coalton-impl/codegen/ast:node-literal
                    :type double-float
                    :value 5.0d0)))
   :subexpr #s(coalton-impl/codegen/ast:node-direct-application
               :type double-float
               :rator-type (double-float → double-float → double-float)
               :rator add-df
               :rands (#s(coalton-impl/codegen/ast:node-variable
                          :type double-float
                          :value x-4321)
                         #s(coalton-impl/codegen/ast:node-variable
                            :type double-float
                            :value x-4321))))

With constant-propagation in place, the constant let bindings are substituted with the literals instead:

#s(coalton-impl/codegen/ast:node-direct-application
   :type double-float
   :rator-type (double-float → double-float → double-float)
   :rator add-df
   :rands (#s(coalton-impl/codegen/ast:node-literal
              :type double-float
              :value 5.0d0)
             #s(coalton-impl/codegen/ast:node-literal
                :type double-float
                :value 5.0d0)))

[stylewarning]

For this PR, my suggestion is to keep it very simple:

• only propagate obvious numerical and boolean constants
• add some conds/"hooks" for places where we can do more elaborate checks (but don't)
• leave out an extensible notion of constantp

I think we should attack constantness one case at a time so we can thoroughly deliberate it. For now, let's just get the basic behavior in.

[stylewarning]

@amorphedstar @digikar99 Any remaining outstanding items?

[digikar99]

boolean constants

Do you mean CL booleans or Coalton booleans? If the former, could you provide a sample code where they get used in Coalton code?