Use unlifted types in Core to replace the STG tag-invariant-rewrite pass
See also:
- #24271: record evaluated-ness info in results of CPR
Background
Since ghc-9.4, we insist that a call-by-value calling convention is used for the strict lifted arguments to Cbv-functions and DataCon workers.
Specifically, these arguments must...
- ...refer directly (no indirections) to an evaluated heap object
- ...be properly-tagged
Notice that these are exactly the same invariants that we demand of
- case-binders
- variables of boxed unlifted type
We exploit this calling convention to elide evaluations of these arguments when generating code for Cbv-functions and likewise when scrutinizing a variable extracted from a strict field of a data constructor, producing smaller and more efficient code. (The latter is extremely valuable for traversals of spine-strict data structures like Data.Set.Set
.)
Our Core-to-Core pipeline discards "redundant" evals with great enthusiasm, in many ways. (See also Note [How untagged pointers can end up in strict fields]
and #15696 (closed) and #20749 and #21741, among probably many other discussions.)
So, today, to actually enforce this calling convention, we:
- eta-expand these functions in CorePrep and
- insert evals of strict arguments at their call sites in the STG tag-invariant-rewrite pass (
Stg.InferTags.Rewrite
) just before code generation (StgToWhatever).- We also perform a simple analysis to avoid inserting evals of arguments that already satisfy 1 and 2.
But it would be really be much simpler and more direct to represent these evaluations and Cbv calling conventions in Core. But then how do we avoid the discarded-redundant-evals problem? Simple.
Proposal
Represent the call-by-value convention of Cbv-functions and strict DataCon workers in their type!
More specifically, introduce a wired-in type Strict# :: Type -> UnliftedType
with the semantics that the possible values of type Strict# a
are exactly the possible values of type a
that satisfy conditions 1 and 2 above. Then, given a declaration data T x y = MkT x !y
, the DataCon worker for MkT
can have type forall x y. x -> Strict# y -> T x y
. It is impossible for Core-to-Core to discard an eval on the second field without angering lint because y
and Strict# y
are different types, with different kinds.
We must explicitly convert between y
and Strict# y
, perhaps with operations like these:
-
toStrict# :: a -> Strict# a
evaluates its argument and returns the result. -
fromStrict# :: Strict# a -> a
is a no-op.
The main difficulty is that we must optimize well in the presence of these operations, or else their use will incur unwanted indirect overheads. For example:
let y = Left x in
case toStrict# y of y' { __DEFAULT ->
... case fromStrict# y' of { Left p -> e1 ; Right q -> e2 } ...
}
==> case-of-known-constructor should not be blocked by toStrict#/fromStrict# noise
let y = Left x in
case toStrict# y of y' { __DEFAULT ->
... e1[p/x] ...
}
The other thing the tag inference pass gives us is information about which components of the result of a function call must satisfy conditions 1 and 2. We can keep this by letting worker-wrapper-for-CPR create Strict#
components of unboxed tuple results where appropriate. Conveniently, CPR analysis already gathers this information because it is needed for nested CPR.
!10252 implements the proposed Strict#
data type. But:
- It currently needs to be rebased, as does !10247 on which it is based.
- It needs a lot of work to improve optimization in the presence of
toStrict#
/fromStrict#
. - It implements strict DataCon fields using
Strict#
as described above, but does not yet touch worker/wrapper and replace the Cbv-function mechanism.