Skip to content

Commit

Permalink
Move inlining logic to a separate file (#422)
Browse files Browse the repository at this point in the history
  • Loading branch information
@eldritchconundrum
eldritchconundrum authored Jun 1, 2024
1 parent 325c7a6 commit 9989859
Show file tree
Hide file tree
Showing 7 changed files with 489 additions and 477 deletions.
1 change: 1 addition & 0 deletions Shader Minifier Library.fsproj
View file
Original file line number Diff line number Diff line change
Expand Up @@ -57,6 +57,7 @@
<Compile Include="src\printer.fs" />
<Compile Include="src\formatter.fs" />
<Compile Include="src\analyzer.fs" />
<Compile Include="src\inlining.fs" />
<Compile Include="src\renamer.fs" />
<Compile Include="src\rewriter.fs" />
<Compile Include="src\preprocessor.fs" />
Expand Down
1 change: 1 addition & 0 deletions shader-minifier-linux.fsproj
View file
Original file line number Diff line number Diff line change
Expand Up @@ -12,6 +12,7 @@
<Compile Include="src\printer.fs" />
<Compile Include="src\formatter.fs" />
<Compile Include="src\analyzer.fs" />
<Compile Include="src\inlining.fs" />
<Compile Include="src\renamer.fs" />
<Compile Include="src\rewriter.fs" />
<Compile Include="src\preprocessor.fs" />
Expand Down
518 changes: 145 additions & 373 deletions src/analyzer.fs
View file

Large diffs are not rendered by default.

7 changes: 7 additions & 0 deletions src/ast.fs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -347,3 +347,10 @@ let stringToJumpKeyword = function
| "discard" -> JumpKeyword.Discard
| "return" -> JumpKeyword.Return
| s -> failwith ("not a keyword: " + s)

let (|ResolvedVariableUse|_|) = function
| Var v ->
match v.Declaration with
| Declaration.Variable vd -> Some (v, vd)
| _ -> None
| _ -> None
314 changes: 314 additions & 0 deletions src/inlining.fs
View file

Large diffs are not rendered by default.

2 changes: 1 addition & 1 deletion src/renamer.fs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -266,7 +266,7 @@ type private RenamerImpl(options: Options.Options) =
// Find all the variables known in varRenames that are used in the block.
// They should be preserved in the renaming environment.
let stillUsedSet =
[for ident in Analyzer.varUsesInStmt options block -> ident.Name]
[for ident in Analyzer.Analyzer(options).varUsesInStmt block -> ident.Name]
|> Seq.choose env.varRenames.TryFind |> set

let varRenames, reusable = env.varRenames |> Map.partition (fun _ id -> stillUsedSet.Contains id)
Expand Down
123 changes: 20 additions & 103 deletions src/rewriter.fs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -4,6 +4,8 @@ open System
open System.Collections.Generic
open Builtin
open Ast
open Inlining
open Analyzer

let private commaSeparatedExprs = List.reduce (fun a b -> FunCall(Op ",", [a; b]))

Expand Down Expand Up @@ -108,8 +110,6 @@ type private RewriterImpl(options: Options.Options, optimizationPass: Optimizati
Some (name, augmentedE)
| _ -> None

let (|ResolvedVariableUse|_|) = Analyzer.(|ResolvedVariableUse|_|)

let simplifyOperator env = function
| FunCall(Op "-", [Int (i1, su)]) -> Int (-i1, su)
| FunCall(Op "-", [FunCall(Op "-", [e])]) -> e
Expand Down Expand Up @@ -181,7 +181,7 @@ type private RewriterImpl(options: Options.Options, optimizationPass: Optimizati
// Swap operands to get rid of parentheses
// x*(y*z) -> y*z*x
| FunCall(Op "*", [NoParen x; FunCall(Op "*", [y; z])])
when Analyzer.isPure x && Analyzer.isPure y && Analyzer.isPure z ->
when Effects.isPure x && Effects.isPure y && Effects.isPure z ->
FunCall(Op "*", [FunCall(Op "*", [y; z]); x]) |> env.fExpr env
// x+(y+z) -> x+y+z
// x+(y-z) -> x+y-z
Expand Down Expand Up @@ -458,14 +458,14 @@ type private RewriterImpl(options: Options.Options, optimizationPass: Optimizati
declElt1.size = declElt2.size &&
declElt1.semantics = declElt2.semantics &&
// The first variable must not be used after the second is declared.
Analyzer.varUsesInStmt options (Block (declAfter2 @ following2)) |> List.forall (fun i -> i.Name <> declElt1.name.Name)
Analyzer(options).varUsesInStmt (Block (declAfter2 @ following2)) |> List.forall (fun i -> i.Name <> declElt1.name.Name)
)

match compatibleDeclElt with
| None -> None
| Some declElt1 ->
options.trace $"{declElt2.name.Loc}: eliminating local variable '{declElt2.name}' by reusing existing local variable '{declElt1.name}'"
for v in Analyzer.varUsesInStmt options (Block (declAfter2 @ following2)) do // Rename all uses of var2 to use var1 instead.
for v in Analyzer(options).varUsesInStmt (Block (declAfter2 @ following2)) do // Rename all uses of var2 to use var1 instead.
if v.Name = declElt2.name.Name then
v.Rename(declElt1.name.Name)
match declElt2.init with
Expand Down Expand Up @@ -509,7 +509,7 @@ type private RewriterImpl(options: Options.Options, optimizationPass: Optimizati
| _ -> true)

let countUsesOfIdentName expr identName =
Analyzer.varUsesInStmt options (Expr expr) |> List.filter (fun i -> i.Name = identName) |> List.length
Analyzer(options).varUsesInStmt (Expr expr) |> List.filter (fun i -> i.Name = identName) |> List.length

let replaceUsesOfIdentByExpr expr identName replacement =
let visitAndReplace _ = function
Expand Down Expand Up @@ -549,7 +549,7 @@ type private RewriterImpl(options: Options.Options, optimizationPass: Optimizati
// Remove unused assignment immediately followed by re-assignment: m=14.;m=58.; -> 14.;m=58.;
| 0 -> Some [Expr init1; assign2] // Transform is safe even if the var is an out parameter.
// Inline this single use of a used-once assignment into the immediately following re-assignment: m=14.;m=58.-m; -> m=58.-14.;
| 1 when Analyzer.isPure init1 && Analyzer.isPure init2 -> // This is ok only if init1 is pure and the part of init2 before using m is pure.
| 1 when Effects.isPure init1 && Effects.isPure init2 -> // This is ok only if init1 is pure and the part of init2 before using m is pure.
let newInit2 = replaceUsesOfIdentByExpr init2 name.Name init1
options.trace $"{name.Loc}: merge consecutive pure assignments to the same local '{name}'"
Some [Expr (FunCall (Op "=", [Var name2; newInit2]))]
Expand All @@ -560,12 +560,12 @@ type private RewriterImpl(options: Options.Options, optimizationPass: Optimizati
when declElt.name.Name = name2.Name ->
match countUsesOfIdentName init2 declElt.name.Name with
| 0 ->
match declElt.init |> Option.map Analyzer.sideEffects |> Option.defaultValue [] with
match declElt.init |> Option.map Effects.sideEffects |> Option.defaultValue [] with
// float m=14;m=58.; -> float m=58.;
| [] -> Some [Decl (ty, [{declElt with init = Some init2}])]
// float m=f();m=58.; -> float m=(f(),58.);
| es -> Some [Decl (ty, [{declElt with init = Some (commaSeparatedExprs (es @ [init2]))}])]
| 1 when Option.forall Analyzer.isPure declElt.init && Analyzer.isPure init2 ->
| 1 when Option.forall Effects.isPure declElt.init && Effects.isPure init2 ->
match declElt.init with
| None -> None // can't replace float a;a=f(a); by float a=f(a);
| Some init1 -> // float m=14.;m=58.-m; -> float m=58.-14.;
Expand All @@ -578,7 +578,7 @@ type private RewriterImpl(options: Options.Options, optimizationPass: Optimizati
// Reduces impure expression statements to their side effects.
let b = b |> List.collect (function
| Expr e ->
match Analyzer.sideEffects e with
match Effects.sideEffects e with
| [] -> [] // Remove pure statements.
| [e] -> [Expr e]
| sideEffects -> [Expr (commaSeparatedExprs sideEffects)]
Expand Down Expand Up @@ -694,8 +694,8 @@ type private RewriterImpl(options: Options.Options, optimizationPass: Optimizati
| e -> e

static let rec removeUnusedFunctions (options: Options.Options) code =
let funcInfos = Analyzer.findFuncInfos options code
let isUnused (funcInfo : Analyzer.FuncInfo) =
let funcInfos = Analyzer(options).findFuncInfos code
let isUnused (funcInfo : FuncInfo) =
let canBeRenamed = not (options.noRenamingList |> List.contains funcInfo.name) // noRenamingList includes "main"
let isCalled = funcInfos |> List.exists (fun n ->
n.callSites
Expand Down Expand Up @@ -738,7 +738,7 @@ let reorderFunctions (options: Options.Options) code =

let rec graphReorder = function // slow, but who cares?
| [] -> []
| (nodes : Analyzer.FuncInfo list) ->
| (nodes : FuncInfo list) ->
// Find a function that doesn't call anything else
let node = nodes |> List.tryFind (fun node -> node.callSites.IsEmpty)
|> Option.defaultWith (fun _ -> failwith "Cannot reorder functions (probably because of a recursion).")
Expand All @@ -749,101 +749,18 @@ let reorderFunctions (options: Options.Options) code =
// Recurse
node.func :: graphReorder nodes

let order = code |> Analyzer.findFuncInfos options |> graphReorder
let order = code |> Analyzer(options).findFuncInfos |> graphReorder
let rest = code |> List.filter (function Function _ -> false | _ -> true)
rest @ order


type [<NoComparison>] ArgumentInlining_Inlining = { // TODO: investigate if/why there's no way to declare a type inside a type in F#
func: TopLevel
argIndex: int
varDecl: VarDecl
argExpr: Expr
}

// Inline the argument of a function call into the function body.
type private ArgumentInlining(options: Options.Options) =

let rec isInlinableExpr = function
// This is different that purity: reading a variable is pure, but non-inlinable in general.
| Var v when v.Name = "true" || v.Name = "false" -> true
| Int _
| Float _ -> true
| FunCall(Var fct, args) -> Builtin.pureBuiltinFunctions.Contains fct.Name && List.forall isInlinableExpr args
| FunCall(Op op, args) -> not (Builtin.assignOps.Contains op) && List.forall isInlinableExpr args
| _ -> false

// Find when functions are always called with the same trivial expr, that can be inlined into the function body.
let findInlinings code: ArgumentInlining_Inlining list =
let mutable argInlinings = []
Analyzer.resolve options code
Analyzer.markWrites options code
let funcInfos = Analyzer.findFuncInfos options code
for funcInfo in funcInfos do
let canBeRenamed = not (options.noRenamingList |> List.contains funcInfo.name) // noRenamingList includes "main"
// If the function is overloaded, removing a parameter could conflict with another overload.
if canBeRenamed && not (funcInfo.funcType.isExternal(options)) && funcInfo.isOverloaded then
let callSites = funcInfos |> List.collect (fun n -> n.callSites) |> List.filter (fun n -> n.prototype = funcInfo.funcType.prototype)
for argIndex, (_, argDecl) in List.indexed funcInfo.funcType.parameters do
match argDecl.name.VarDecl with
| Some varDecl when not varDecl.ty.isOutOrInout -> // Only inline 'in' parameters.
let argExprs = callSites |> List.map (fun c -> c.argExprs |> List.item argIndex) |> List.distinct
match argExprs with
| [argExpr] when isInlinableExpr argExpr -> // The argExpr must always be the same at all call sites.
options.trace $"{varDecl.decl.name.Loc}: inlining expression '{Printer.exprToS argExpr}' into argument '{Printer.debugDecl varDecl.decl}' of '{Printer.debugFunc funcInfo.funcType}'"
argInlinings <- {func=funcInfo.func; argIndex=argIndex; varDecl=varDecl; argExpr=argExpr} :: argInlinings
| _ -> ()
| _ -> ()
argInlinings

let apply (didInline: bool ref) code =
let argInlinings = findInlinings code

let removeInlined func list =
list
|> List.indexed
|> List.filter (fun (idx, _) -> not (argInlinings |> List.exists (fun inl -> inl.func = func && inl.argIndex = idx)))
|> List.map snd

let applyExpr _ = function
| FunCall (Var v, argExprs) as f ->
// Remove the argument expression from the call site.
match v.Declaration with
| Declaration.UserFunction fd -> FunCall (Var v, removeInlined fd.func argExprs)
| _ -> f
| x -> x

let applyTopLevel = function
| Function(fct, body) as f ->
// Handle argument inlining for other functions called by f.
let _, body = mapStmt (BlockLevel.FunctionRoot fct) (mapEnvExpr options applyExpr) body
// Handle argument inlining for f. Remove the parameter from the declaration.
let fct = {fct with args = removeInlined f fct.args}
// Handle argument inlining for f. Insert in front of the body a declaration for each inlined argument.
let decls =
argInlinings
|> List.filter (fun inl -> inl.func = f)
|> List.map (fun inl -> Decl (
{inl.varDecl.ty with typeQ = inl.varDecl.ty.typeQ |> List.filter ((=) "const")},
[{inl.varDecl.decl with init = Some inl.argExpr}]))
Function(fct, Block (decls @ body.asStmtList))
| tl -> tl

if argInlinings.IsEmpty then
code
else
let code = code |> List.map applyTopLevel
didInline.Value <- true
code
member _.Apply = apply

let rec private iterateSimplifyAndInline (options: Options.Options) optimizationPass passCount li =
let li = if not options.noRemoveUnused then RewriterImpl.RemoveUnusedFunctions options li else li
Analyzer.resolve options li
Analyzer.markWrites options li
Analyzer(options).resolve li
Analyzer(options).markWrites li
if not options.noInlining then
(Analyzer.FunctionInlining(options)).MarkInlinableFunctions li
(Analyzer.VariableInlining(options)).MarkInlinableVariables li
FunctionInlining(options).MarkInlinableFunctions li
VariableInlining(options).MarkInlinableVariables li
let didInline = ref false
let before = Printer.print li
let rewriter = RewriterImpl(options, optimizationPass)
Expand All @@ -854,7 +771,7 @@ let rec private iterateSimplifyAndInline (options: Options.Options) optimization
| Function (funcType, _) -> not funcType.fName.ToBeInlined || funcType.fName.Name.StartsWith("i_")
| _ -> true)

let li = if options.noInlining then li else (ArgumentInlining(options)).Apply didInline li
let li = if options.noInlining then li else ArgumentInlining(options).Apply didInline li

if passCount > 20 then
options.trace $"! possible unstable loop in change detection. stopping analysis."
Expand All @@ -870,4 +787,4 @@ let simplify options li =
li
|> iterateSimplifyAndInline options OptimizationPass.First 1
|> iterateSimplifyAndInline options OptimizationPass.Second 1
|> (RewriterImpl(options, OptimizationPass.First)).Cleanup
|> RewriterImpl(options, OptimizationPass.First).Cleanup

0 comments on commit 9989859

Please sign in to comment.