Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
10 changes: 10 additions & 0 deletions changelog.d/20260712_190000_unisay_alias_to_always_binding.md
Original file line number Diff line number Diff line change
@@ -0,0 +1,10 @@
### Fixed

- The top-level inliner keeps a bare-`Ref` alias to an `@inline always`
binding as the single materialization point instead of dissolving it:
substituting the alias multiplied the target's use sites right before
`Always` pasted its body into every one of them, duplicating the body
(a lifted foreign's lambda, for example) across all alias use sites.
The `Always` directive is now also consulted by name at the top level,
so a binding that merely received an always-annotated body during an
earlier paste no longer turns unconditionally inlinable itself (#171).
7 changes: 6 additions & 1 deletion lib/Language/PureScript/Backend/IR/Inliner.hs
Original file line number Diff line number Diff line change
Expand Up @@ -64,7 +64,12 @@ stages:
rewrites may strip an annotation off its node, so decisions key off
names — and the optimizer consults the resulting policy:

* @Just Always@ on a root forces inlining ('isInlinableExpr');
* @Just Always@ on a root forces inlining: the top-level inliner
consults it by name (@policyAlways@) and keeps a bare-Ref alias
to such a name as the single materialization point — dissolving
the alias would multiply the target's use sites right before
Always pastes its body into each (issue #171); the local rules
read the root annotation directly ('isInlinableExpr');
* @Never@ names are never pasted ('withBinding', the call-site
rules, and the uncurry split all veto them);
* @Arity n@ names are pasted exactly at call sites applying at
Expand Down
54 changes: 43 additions & 11 deletions lib/Language/PureScript/Backend/IR/Optimizer.hs
Original file line number Diff line number Diff line change
Expand Up @@ -357,7 +357,11 @@ annotations after optimization.
See Note [Inline annotations and inlining heuristics].
-}
data InlinePolicy = InlinePolicy
{ policyNever ∷ Set QName
{ policyAlways ∷ Set QName
{- ^ pasted at every use site; a bare-Ref alias to such a name is
never dissolved (issue #171)
-}
, policyNever ∷ Set QName
-- ^ never pasted anywhere
, policyArity ∷ Map QName Natural
-- ^ pasted exactly at call sites applying at least N arguments
Expand All @@ -382,6 +386,7 @@ collectInlinePolicy UberModule {uberModuleBindings, uberModuleForeigns} =
fromBinding (qname, expr) = rootPolicy <> fieldsPolicy
where
rootPolicy = case getAnn expr of
Just Always → mempty {policyAlways = Set.singleton qname}
Just Never → mempty {policyNever = Set.singleton qname}
Just (Arity n) → mempty {policyArity = Map.singleton qname n}
_ → mempty
Expand Down Expand Up @@ -501,6 +506,27 @@ optimizeModule inlining policy UberModule {..} = runWriterT do
qname `Set.member` policyNever policy
|| qname `Map.member` policyArity policy

-- The top-level counterpart of 'isInlinableExpr', diverging from it
-- twice (issue #171). The Always directive is consulted by name —
-- 'policyAlways', not the RHS root annotation, which an earlier paste
-- may have planted there: a binding that merely received an
-- always-annotated body must not itself turn unconditionally
-- inlinable. And a bare-Ref alias to an @inline always@ binding is
-- never dissolved: substituting it would multiply the target's use
-- sites right before Always pastes its body into every one of them,
-- destroying the alias that is the better materialization point on
-- both size and speed. The target's body pastes into the surviving
-- alias instead.
topLevelInlinable ∷ QName → Exp → Bool
topLevelInlinable qname expr =
qname `Set.member` policyAlways policy
|| (isInlinableValue expr && not (aliasesAlwaysBinding expr))

aliasesAlwaysBinding ∷ Exp → Bool
aliasesAlwaysBinding = \case
Ref _ ref → maybe False (`Set.member` policyAlways policy) (refQName ref)
_ → False

-- Whether 'withBinding' may drop a whole top-level binding by inlining it
-- into its use sites. Off exactly when call-site inlining is on, because the
-- two are unsound together: 'inlineEnv' is a snapshot taken before this run
Expand Down Expand Up @@ -545,7 +571,7 @@ optimizeModule inlining policy UberModule {..} = runWriterT do
if mayInlineWholeBinding
&& not (vetoedWholeBinding qname)
&& not (isForeignImport expr)
&& (isInlinableExpr expr || isUsedOnce)
&& (topLevelInlinable qname expr || isUsedOnce)
then do
-- The binding is dropped from the module in favor of the
-- substituted copies: a rewrite even when it had no
Expand Down Expand Up @@ -1703,9 +1729,21 @@ position.
-- See Note [Inline annotations and inlining heuristics]
-- and Note [Complexity and Capture gate inlining]
isInlinableExpr ∷ Exp → Bool
isInlinableExpr expr =
hasInlineAnnotation expr
|| isRef expr
isInlinableExpr expr = hasInlineAnnotation expr || isInlinableValue expr
where
hasInlineAnnotation ∷ Exp → Bool
hasInlineAnnotation =
getAnn >>> \case
Just Always → True
_ → False

{- | The structural tiers of 'isInlinableExpr' — everything but the
Always annotation, which the top-level inliner consults by name instead
(see 'InlinePolicy' and issue #171).
-}
isInlinableValue ∷ Exp → Bool
isInlinableValue expr =
isRef expr
|| isNonRecursiveLiteral expr
|| isCheapProjection expr
where
Expand All @@ -1714,12 +1752,6 @@ isInlinableExpr expr =
Ref {} → True
_ → False

hasInlineAnnotation ∷ Exp → Bool
hasInlineAnnotation =
getAnn >>> \case
Just Always → True
_ → False

-- The Deref tier. The explicit disjuncts above are subsumed for the
-- shapes they share (a Ref, a short scalar), but kept: they also admit
-- what the tier prices differently (a long string literal).
Expand Down
40 changes: 40 additions & 0 deletions test/Language/PureScript/Backend/IR/Optimizer/Spec.hs
Original file line number Diff line number Diff line change
Expand Up @@ -927,6 +927,46 @@ spec = describe "IR Optimizer" do
annotateShow optimized
fooKept === [QName mainModule (Name "foo")]

describe "keeps a bare-Ref alias to an @inline always binding (#171)" do
test "the alias stays the single materialization point" do
let semiringModule = moduleNameFromString "Data.Semiring"
mainModule = moduleNameFromString "Main"
intAddName = QName semiringModule (Name "intAdd")
addName = QName mainModule (Name "add")
-- The shape ForeignLift gives a lifted foreign: a lambda marked
-- @inline always@ so its call sites beta-reduce. Unary, so the
-- uncurry split leaves it alone and the test sees only the
-- alias interaction.
liftedIntAdd =
setAnn (Just Always) . abstraction (paramNamed (Name "x")) $
primBinOp PrimAdd (refLocal (Name "x")) (refLocal (Name "x"))
original =
Linker.UberModule
{ uberModuleForeigns = []
, uberModuleBindings =
[ Standalone (intAddName, liftedIntAdd)
, Standalone
(addName, refImported semiringModule (Name "intAdd"))
]
, uberModuleExports =
[ (Name "main1", refImported mainModule (Name "add"))
, (Name "main2", refImported mainModule (Name "add"))
]
}
optimized ←
either (fail . show) pure (optimizedUberModuleChecked original)
annotateShow optimized
-- Dissolving the alias would take the Always target's use sites
-- from one to two right before Always pastes its body into every
-- one of them. Instead the alias survives — the body materializes
-- once, in the alias — and both exports keep referencing it.
[qn | Standalone (qn, _) ← Linker.uberModuleBindings optimized]
=== [addName]
Linker.uberModuleExports optimized
=== [ (Name "main1", refImported mainModule (Name "add"))
, (Name "main2", refImported mainModule (Name "add"))
]

describe "gates inlining by Complexity and Capture (issue #231)" do
let main' = moduleNameFromString "Main"
ext = moduleNameFromString "Ext"
Expand Down
28 changes: 15 additions & 13 deletions test/ps/output/Golden.ArrayOfUnits.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,13 +4,19 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Data.Unit", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Unit" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Unit.purs"
[ ( Just Always, Name "unit" ) ]
( ModuleName "Data.Unit" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Unit.purs"
[ ( Just Never, Name "unit" ) ]
), Standalone
( QName
{ qnameModuleName = ModuleName "Data.Unit", qnameName = Name "unit"
}, ObjectProp ( Just Never )
( Ref Nothing ( Imported ( ModuleName "Data.Unit" ) ( Name "foreign" ) ) )
( PropName "unit" )
), Standalone
( QName
{ qnameModuleName = ModuleName "Data.Show", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Show" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Show.purs"
( ModuleName "Data.Show" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Show.purs"
[ ( Nothing, Name "showIntImpl" ) ]
), Standalone
( QName
Expand Down Expand Up @@ -310,13 +316,10 @@ UberModule
( Name "main", Let Nothing
( Standalone
( Nothing, Name "arr$0", LiteralArray Nothing
[ ObjectProp ( Just Always )
( Ref Nothing ( Imported ( ModuleName "Data.Unit" ) ( Name "foreign" ) ) )
( PropName "unit" ), ObjectProp ( Just Always )
( Ref Nothing ( Imported ( ModuleName "Data.Unit" ) ( Name "foreign" ) ) )
( PropName "unit" ), ObjectProp ( Just Always )
( Ref Nothing ( Imported ( ModuleName "Data.Unit" ) ( Name "foreign" ) ) )
( PropName "unit" )
[ Ref Nothing
( Imported ( ModuleName "Data.Unit" ) ( Name "unit" ) ), Ref Nothing
( Imported ( ModuleName "Data.Unit" ) ( Name "unit" ) ), Ref Nothing
( Imported ( ModuleName "Data.Unit" ) ( Name "unit" ) )
]
) :| []
)
Expand Down Expand Up @@ -421,9 +424,8 @@ UberModule
)
( PropName "pure" )
)
( ObjectProp ( Just Always )
( Ref Nothing ( Imported ( ModuleName "Data.Unit" ) ( Name "foreign" ) ) )
( PropName "unit" ) :| []
( Ref Nothing
( Imported ( ModuleName "Data.Unit" ) ( Name "unit" ) ) :| []
) :| []
)
)
Expand Down
9 changes: 5 additions & 4 deletions test/ps/output/Golden.ArrayOfUnits.Test/golden.lua
Original file line number Diff line number Diff line change
Expand Up @@ -17,6 +17,7 @@ local function PSLUA_runtime_lazy(name)
end
end
local Data_Unit_foreign = { unit = {} }
local Data_Unit_unit = Data_Unit_foreign.unit
local Data_Show_foreign = { showIntImpl = function(n) return tostring(n) end }
local Data_Foldable_foreign = {
foldrArray = function(f)
Expand Down Expand Up @@ -109,9 +110,9 @@ local Effect_Console_logShow_S_w = function(dictShow, a)
end
return (function()
local arr_S_0 = {
[1] = Data_Unit_foreign.unit,
[2] = Data_Unit_foreign.unit,
[3] = Data_Unit_foreign.unit
[1] = Data_Unit_unit,
[2] = Data_Unit_unit,
[3] = Data_Unit_unit
}
return function()
local _ = Data_Foldable_foldableArray.foldr(function(x_S_940)
Expand All @@ -127,7 +128,7 @@ return (function()
end)()(Effect_Console_logShow_S_w({
show = function() return "unit" end
}, x_S_940))
end)(Effect_applicativeEffect.pure(Data_Unit_foreign.unit))(arr_S_0)()
end)(Effect_applicativeEffect.pure(Data_Unit_unit))(arr_S_0)()
return Effect_Console_logShow_S_w({
show = Data_Show_foreign.showIntImpl
}, Data_Foldable_foldableArray.foldl(function(c_S_372_S_914)
Expand Down
2 changes: 1 addition & 1 deletion test/ps/output/Golden.ArrayPatternMatch.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Data.Show", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Show" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Show.purs"
( ModuleName "Data.Show" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Show.purs"
[ ( Nothing, Name "showIntImpl" ) ]
), Standalone
( QName
Expand Down
2 changes: 1 addition & 1 deletion test/ps/output/Golden.BugListGenericEq.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Record.Unsafe", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Record.Unsafe" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Record/Unsafe.purs"
( ModuleName "Record.Unsafe" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Record/Unsafe.purs"
[ ( Nothing, Name "unsafeGet" ) ]
), Standalone
( QName
Expand Down
2 changes: 1 addition & 1 deletion test/ps/output/Golden.CharLiterals.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Data.Show", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Show" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Show.purs"
( ModuleName "Data.Show" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Show.purs"
[ ( Nothing, Name "showCharImpl" ) ]
), Standalone
( QName
Expand Down
2 changes: 1 addition & 1 deletion test/ps/output/Golden.DerivedFunctor.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Data.Show", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Show" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Show.purs"
( ModuleName "Data.Show" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Show.purs"
[ ( Nothing, Name "showIntImpl" ) ]
), Standalone
( QName
Expand Down
2 changes: 1 addition & 1 deletion test/ps/output/Golden.DirectiveAccessor.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Data.Show", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Show" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Show.purs"
( ModuleName "Data.Show" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Show.purs"
[ ( Nothing, Name "showIntImpl" ) ]
), Standalone
( QName
Expand Down
2 changes: 1 addition & 1 deletion test/ps/output/Golden.DirectiveArity.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Data.Show", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Show" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Show.purs"
( ModuleName "Data.Show" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Show.purs"
[ ( Nothing, Name "showIntImpl" ) ]
), Standalone
( QName
Expand Down
2 changes: 1 addition & 1 deletion test/ps/output/Golden.Fibonacci.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Data.Show", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Show" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Show.purs"
( ModuleName "Data.Show" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Show.purs"
[ ( Nothing, Name "showIntImpl" ) ]
), Standalone
( QName
Expand Down
2 changes: 1 addition & 1 deletion test/ps/output/Golden.FieldCaching.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Data.Show", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Show" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Show.purs"
( ModuleName "Data.Show" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Show.purs"
[ ( Nothing, Name "showIntImpl" ) ]
), Standalone
( QName
Expand Down
22 changes: 11 additions & 11 deletions test/ps/output/Golden.FloatIn.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,13 +4,19 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Data.Unit", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Unit" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Unit.purs"
[ ( Just Always, Name "unit" ) ]
( ModuleName "Data.Unit" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Unit.purs"
[ ( Just Never, Name "unit" ) ]
), Standalone
( QName
{ qnameModuleName = ModuleName "Data.Unit", qnameName = Name "unit"
}, ObjectProp ( Just Never )
( Ref Nothing ( Imported ( ModuleName "Data.Unit" ) ( Name "foreign" ) ) )
( PropName "unit" )
), Standalone
( QName
{ qnameModuleName = ModuleName "Data.Show", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Show" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Show.purs"
( ModuleName "Data.Show" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Show.purs"
[ ( Nothing, Name "showIntImpl" ) ]
), Standalone
( QName
Expand Down Expand Up @@ -69,17 +75,11 @@ UberModule
( PrimBinOp Nothing PrimAdd
( AppN Nothing
( Ref Nothing ( Local ( Name "f" ) ) )
( ObjectProp ( Just Always )
( Ref Nothing ( Imported ( ModuleName "Data.Unit" ) ( Name "foreign" ) ) )
( PropName "unit" ) :| []
)
( Ref Nothing ( Imported ( ModuleName "Data.Unit" ) ( Name "unit" ) ) :| [] )
)
( AppN Nothing
( Ref Nothing ( Local ( Name "f" ) ) )
( ObjectProp ( Just Always )
( Ref Nothing ( Imported ( ModuleName "Data.Unit" ) ( Name "foreign" ) ) )
( PropName "unit" ) :| []
)
( Ref Nothing ( Imported ( ModuleName "Data.Unit" ) ( Name "unit" ) ) :| [] )
)
)
)
Expand Down
3 changes: 2 additions & 1 deletion test/ps/output/Golden.FloatIn.Test/golden.lua
Original file line number Diff line number Diff line change
@@ -1,5 +1,6 @@
local M = {}
local Data_Unit_foreign = { unit = {} }
local Data_Unit_unit = Data_Unit_foreign.unit
local Data_Show_foreign = { showIntImpl = function(n) return tostring(n) end }
local Data_Show_showIntImpl = Data_Show_foreign.showIntImpl
local Effect_Console_foreign = {
Expand All @@ -14,7 +15,7 @@ local Golden_FloatIn_Test_pickShared_S_w = function(useIt, n)
if useIt then
local shared = Golden_FloatIn_Test_tick(n)
local f = function() return shared + shared end
return f(Data_Unit_foreign.unit) + f(Data_Unit_foreign.unit)
return f(Data_Unit_unit) + f(Data_Unit_unit)
else
return 0
end
Expand Down
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Data.Show", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Data.Show" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Data/Show.purs"
( ModuleName "Data.Show" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Data/Show.purs"
[ ( Nothing, Name "showIntImpl" ) ]
), Standalone
( QName
Expand Down
2 changes: 1 addition & 1 deletion test/ps/output/Golden.GenericEqTwoTypes.Test/golden.ir
Original file line number Diff line number Diff line change
Expand Up @@ -4,7 +4,7 @@ UberModule
( QName
{ qnameModuleName = ModuleName "Record.Unsafe", qnameName = Name "foreign"
}, ForeignImport Nothing
( ModuleName "Record.Unsafe" ) ".spago/p/prelude/26c058c2a053cf4dd7240f0d822ec096c0fecbe1/src/Record/Unsafe.purs"
( ModuleName "Record.Unsafe" ) ".spago/p/prelude/5718c84fdde6247749cb053e816df696c30fe691/src/Record/Unsafe.purs"
[ ( Nothing, Name "unsafeGet" ) ]
), Standalone
( QName
Expand Down
Loading