CommonSubexpressionElimination

Share repeated expressions by introducing a strict UPLC binding, using Plutus 1.63.0.0's ancestor-or-self rule. In the examples below, let x = e in body means [(lam x body) e]; e is evaluated before body, even when the uses of x are delayed. For example, let x = Error in Delay(x) fails immediately, whereas Delay(Error) is a value.

// When sharing pays, keep one copy of e and replace its uses with variables:
Constr(0, [e, e])  =>  let x = e in Constr(0, [x, x])

// An existing strict occurrence can also supply a deferred use:
Constr(0, [e, Delay(e)])  =>  let x = e in Constr(0, [x, Delay(x)])

// No strict occurrence outside the delays: do not move e out of them.
Constr(0, [Delay(e), Delay(e)])

==Safety: where may the binding go?== Lambda bodies, delayed bodies and individual Case branches are separate evaluation regions. Other children inherit their parent's region, including the body of an immediately applied lambda (a strict let). A group must contain an occurrence in its outermost region; occurrences in descendant regions can join it. Sibling regions alone cannot justify an outer binding. Otherwise extracting, for example, a failing e from an unused delay would make a successful program fail. The same placement rule applies to every candidate, including constants:

LamAbs(a, Constr(0, [e(a), e(a)]))
 => LamAbs(a, let x = e(a) in Constr(0, [x, x]))  // stay inside the lambda

let a = e in Constr(0, [a, e])
 => let x = e in (let a = x in Constr(0, [a, x])) // applied lambda is strict

Case(tag, [e, e, 0])  // no outer occurrence of e; selecting branch 2 must not run e
Constr(0, [Delay(largeConstant), Delay(largeConstant)])
 // No special constant-hoisting exception: the two constant uses stay in separate regions.
 // Sharing the whole Delay values is allowed; that does not evaluate their bodies.

Like Plutus CSE, this preserves results and success/failure, not trace multiplicity, trace order, failure messages or exact budgets. A region is not an evaluation-order barrier: sharing may move work earlier within it. For example, with e = trace("B", 1) and a = trace("A", 0), sharing e in Constr(0, [a, e, e]) can change logs from ["A", "B", "B"] to ["B", "A"] while returning the same constructor. If a and e both fail, moving e first can change which failure is reported, but still fails. Even sharing a constant adds Apply/LamAbs/Var work, so exact budgets are not preserved.

No builtin-totality or name-prefix assumptions are needed: divideInteger n d can be a candidate even when d might be zero, provided placement is safe and sharing pays. Renaming n to __partial_n does not change that decision.

==Profitability: should we introduce the binding?== Safe placement alone is insufficient. SharingCost prices estimated reference-script bits saved minus the extra binding's execution fee for values. Repeated computations such as f(xs) are also shared when that estimate is negative: the callee's avoided work is unknown, so this is a runtime-sharing preference, not a prediction of lower total fees. Each round takes the greatest eligible estimate, then recollects on the changed tree. For example, three uses of a 54-bit constant save (3 - 1) * 54 - 3 * 12 - 8 = 64 estimated bits: remove two copies, insert three variables, and pay the Apply/LamAbs tags. The default fee estimate subtracts about 20.77 lovelace of binding work from 120 lovelace of reference-size savings. Two uses of an 18-bit integer constant instead save 18 - 24 - 8 = -14 bits and are rejected. See docs/design/cse-placement.md for the contract and pricing assumptions.