lift and deduplicate constants

[sorear]

(descoped from #773)

Given a potentially hot function, we should not allocate data in the function which is known to be constant.

Define a "deep constant" to be a closLang expression consisting entirely of Const (integers), String, WordFromInt, and Cons (i.e. all children of a deep constant must be deep constants). Define a "nontrivial maximal deep constant" to be a deep constant which is not contained in a larger deep constant and which requires allocation (is not a Cons with 0 children or a Const in fixnum range.

The (symbols PR) compiler has:

• 57 nontrivial maximal Const, 5 unique
• 3336 nontrivial maximal Cons, 2058 unique
• 866 nontrivial maximal String, 589 unique
• 2254 nontrivial maximal WordFromInt, 121 unique

Total: 2773 unique liftable constants used 6513 times. Of the constants used more than once, there are 624 unique constants; the largest duplicated constant has 39 subobjects (it appears to be related to the initial type environment), and only 697/3740 duplicated constants involve more than one heap object.

Doing only lifting would be a performance improvement but a code size regression since each lifted constant needs to be allocated a global, stored, and loaded (20+ instructions currently, 4 after #797). With deduplication as well this will be marginal currently and a noticeable win with #797.

With the current setup of the semantics this has to be done in closLang as later stages represent strings non-anonymously.

[myreen]

This sounds like a good idea to me.

In your text, you say that this is "to be done in closLang". I agree that it cannot be done later for the reasons you mention. However, it isn't clear to me why it cannot be done earlier. It could even be done as a source-to-source transformation. By doing it as a source-to-source transformation you turn the problem of shifting global numbers to one about keeping track of unused source-level names. I'm not saying one is better than the other, I'm just mentioning this so that all options are considered. Perhaps FlatLang is a nicer place for this transformation because FlatLang avoids ClosLang's complications will multi-argument closures.

Wherever this optimisation happens, in my opinion, it ought to be a compilation pass of its own because it's doing something slightly fiddly.

[sorear]

flatLang has richer constructor values so you wouldn't be able to share as many values. I'm not sure if this matters.

[myreen]

Ah, that makes sense. You are right that certain datatype constructors that are strictly different at source and FlatLang might turn into the same representation in ClosLang and thus allow for more sharing at the ClosLang level. However, I suspect such coincidences are very rare, particularly for larger constants.

[myreen]

The commits in #889 make progress on this issue. However, the commits in #889 do not attempt to lift the constants.