futhark 0.19.6 → 0.19.7

raw patch · 181 files changed

+13121/−13244 lines, 181 filesdep +futhark-datadep +futhark-serverPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: futhark-data, futhark-server

API changes (from Hackage documentation)

Files

• docs/c-api.rst +10/−1
• docs/man/futhark-literate.rst +2/−2
• docs/server-protocol.rst +16/−4
• docs/usage.rst +32/−0
• futhark.cabal +33/−29
• rts/c/server.h +8/−0
• src/Futhark/Actions.hs +10/−10
• src/Futhark/Analysis/Alias.hs +27/−27
• src/Futhark/Analysis/DataDependencies.hs +3/−3
• src/Futhark/Analysis/HORep/MapNest.hs +22/−22
• src/Futhark/Analysis/HORep/SOAC.hs +30/−30
• src/Futhark/Analysis/Interference.hs +326/−0
• src/Futhark/Analysis/LastUse.hs +161/−0
• src/Futhark/Analysis/Metrics.hs +6/−6
• src/Futhark/Analysis/PrimExp/Convert.hs +2/−2
• src/Futhark/Analysis/PrimExp/Simplify.hs +7/−7
• src/Futhark/Analysis/Rephrase.hs +15/−15
• src/Futhark/Analysis/SymbolTable.hs +96/−96
• src/Futhark/Analysis/UsageTable.hs +7/−7
• src/Futhark/Bench.hs +6/−3
• src/Futhark/Binder.hs +67/−67
• src/Futhark/Binder/Class.hs +38/−38
• src/Futhark/CLI/Autotune.hs +1/−1
• src/Futhark/CLI/Bench.hs +33/−17
• src/Futhark/CLI/Datacmp.hs +3/−2
• src/Futhark/CLI/Dataset.hs +30/−26
• src/Futhark/CLI/Dev.hs +77/−71
• src/Futhark/CLI/Literate.hs +9/−7
• src/Futhark/CLI/Pkg.hs +9/−0
• src/Futhark/CLI/Test.hs +14/−11
• src/Futhark/CodeGen/Backends/CCUDA.hs +2/−2
• src/Futhark/CodeGen/Backends/COpenCL.hs +2/−2
• src/Futhark/CodeGen/Backends/GenericC.hs +85/−91
• src/Futhark/CodeGen/Backends/GenericC/CLI.hs +11/−11
• src/Futhark/CodeGen/Backends/GenericC/Server.hs +24/−7
• src/Futhark/CodeGen/Backends/GenericPython.hs +28/−27
• src/Futhark/CodeGen/Backends/MulticoreC.hs +6/−4
• src/Futhark/CodeGen/Backends/PyOpenCL.hs +3/−2
• src/Futhark/CodeGen/Backends/PyOpenCL/Boilerplate.hs +1/−1
• src/Futhark/CodeGen/Backends/SimpleRep.hs +3/−3
• src/Futhark/CodeGen/ImpCode.hs +16/−13
• src/Futhark/CodeGen/ImpCode/GPU.hs +266/−0
• src/Futhark/CodeGen/ImpCode/Kernels.hs +0/−266
• src/Futhark/CodeGen/ImpCode/OpenCL.hs +2/−2
• src/Futhark/CodeGen/ImpGen.hs +193/−197
• src/Futhark/CodeGen/ImpGen/CUDA.hs +4/−4
• src/Futhark/CodeGen/ImpGen/GPU.hs +431/−0
• src/Futhark/CodeGen/ImpGen/GPU/Base.hs +1785/−0
• src/Futhark/CodeGen/ImpGen/GPU/SegHist.hs +1151/−0
• src/Futhark/CodeGen/ImpGen/GPU/SegMap.hs +61/−0
• src/Futhark/CodeGen/ImpGen/GPU/SegRed.hs +842/−0
• src/Futhark/CodeGen/ImpGen/GPU/SegScan.hs +68/−0
• src/Futhark/CodeGen/ImpGen/GPU/SegScan/SinglePass.hs +565/−0
• src/Futhark/CodeGen/ImpGen/GPU/SegScan/TwoPass.hs +506/−0
• src/Futhark/CodeGen/ImpGen/GPU/ToOpenCL.hs +888/−0
• src/Futhark/CodeGen/ImpGen/GPU/Transpose.hs +386/−0
• src/Futhark/CodeGen/ImpGen/Kernels.hs +0/−431
• src/Futhark/CodeGen/ImpGen/Kernels/Base.hs +0/−1803
• src/Futhark/CodeGen/ImpGen/Kernels/SegHist.hs +0/−1151
• src/Futhark/CodeGen/ImpGen/Kernels/SegMap.hs +0/−61
• src/Futhark/CodeGen/ImpGen/Kernels/SegRed.hs +0/−838
• src/Futhark/CodeGen/ImpGen/Kernels/SegScan.hs +0/−68
• src/Futhark/CodeGen/ImpGen/Kernels/SegScan/SinglePass.hs +0/−489
• src/Futhark/CodeGen/ImpGen/Kernels/SegScan/TwoPass.hs +0/−506
• src/Futhark/CodeGen/ImpGen/Kernels/ToOpenCL.hs +0/−888
• src/Futhark/CodeGen/ImpGen/Kernels/Transpose.hs +0/−386
• src/Futhark/CodeGen/ImpGen/Multicore/Base.hs +9/−29
• src/Futhark/CodeGen/ImpGen/Multicore/SegHist.hs +1/−1
• src/Futhark/CodeGen/ImpGen/OpenCL.hs +4/−4
• src/Futhark/CodeGen/SetDefaultSpace.hs +4/−4
• src/Futhark/Compiler.hs +4/−4
• src/Futhark/Compiler/CLI.hs +2/−2
• src/Futhark/Construct.hs +76/−76
• src/Futhark/IR.hs +1/−4
• src/Futhark/IR/Aliases.hs +69/−72
• src/Futhark/IR/Decorations.hs +0/−92
• src/Futhark/IR/GPU.hs +61/−0
• src/Futhark/IR/GPU/Kernel.hs +346/−0
• src/Futhark/IR/GPU/Simplify.hs +113/−0
• src/Futhark/IR/GPU/Sizes.hs +88/−0
• src/Futhark/IR/GPUMem.hs +111/−0
• src/Futhark/IR/Kernels.hs +0/−62
• src/Futhark/IR/Kernels/Kernel.hs +0/−346
• src/Futhark/IR/Kernels/Simplify.hs +0/−113
• src/Futhark/IR/Kernels/Sizes.hs +0/−88
• src/Futhark/IR/KernelsMem.hs +0/−111
• src/Futhark/IR/MC.hs +4/−5
• src/Futhark/IR/MC/Op.hs +29/−29
• src/Futhark/IR/MCMem.hs +6/−6
• src/Futhark/IR/Mem.hs +49/−50
• src/Futhark/IR/Mem/Simplify.hs +35/−35
• src/Futhark/IR/Parse.hs +70/−67
• src/Futhark/IR/Pretty.hs +35/−35
• src/Futhark/IR/Prop.hs +51/−30
• src/Futhark/IR/Prop/Aliases.hs +10/−16
• src/Futhark/IR/Prop/Names.hs +69/−69
• src/Futhark/IR/Prop/Patterns.hs +4/−4
• src/Futhark/IR/Prop/Reshape.hs +1/−1
• src/Futhark/IR/Prop/Scope.hs +61/−61
• src/Futhark/IR/Prop/TypeOf.hs +10/−10
• src/Futhark/IR/Rep.hs +92/−0
• src/Futhark/IR/SOACS.hs +5/−6
• src/Futhark/IR/SOACS/SOAC.hs +75/−75
• src/Futhark/IR/SOACS/Simplify.hs +24/−24
• src/Futhark/IR/SegOp.hs +145/−135
• src/Futhark/IR/Seq.hs +4/−5
• src/Futhark/IR/SeqMem.hs +6/−8
• src/Futhark/IR/Syntax.hs +75/−74
• src/Futhark/IR/Syntax/Core.hs +15/−1
• src/Futhark/IR/Traversals.hs +32/−32
• src/Futhark/Internalise/Defunctionalise.hs +16/−20
• src/Futhark/Internalise/Exps.hs +6/−5
• src/Futhark/Internalise/Monad.hs +1/−1
• src/Futhark/Optimise/BlkRegTiling.hs +22/−22
• src/Futhark/Optimise/CSE.hs +69/−69
• src/Futhark/Optimise/DoubleBuffer.hs +57/−57
• src/Futhark/Optimise/Fusion/Composing.hs +16/−16
• src/Futhark/Optimise/Fusion/LoopKernel.hs +3/−3
• src/Futhark/Optimise/InPlaceLowering.hs +64/−64
• src/Futhark/Optimise/InPlaceLowering/LowerIntoStm.hs +45/−45
• src/Futhark/Optimise/InPlaceLowering/SubstituteIndices.hs +33/−33
• src/Futhark/Optimise/InliningDeadFun.hs +1/−1
• src/Futhark/Optimise/ReuseAllocations.hs +255/−0
• src/Futhark/Optimise/ReuseAllocations/GreedyColoring.hs +61/−0
• src/Futhark/Optimise/Simplify.hs +39/−39
• src/Futhark/Optimise/Simplify/Engine.hs +177/−177
• src/Futhark/Optimise/Simplify/Lore.hs +0/−284
• src/Futhark/Optimise/Simplify/Rep.hs +278/−0
• src/Futhark/Optimise/Simplify/Rule.hs +88/−88
• src/Futhark/Optimise/Simplify/Rules.hs +11/−11
• src/Futhark/Optimise/Simplify/Rules/BasicOp.hs +6/−6
• src/Futhark/Optimise/Simplify/Rules/ClosedForm.hs +16/−16
• src/Futhark/Optimise/Simplify/Rules/Index.hs +1/−1
• src/Futhark/Optimise/Simplify/Rules/Loop.hs +14/−14
• src/Futhark/Optimise/Simplify/Rules/Simple.hs +18/−18
• src/Futhark/Optimise/Sink.hs +41/−41
• src/Futhark/Optimise/TileLoops.hs +91/−103
• src/Futhark/Optimise/TileLoops/Shared.hs +38/−15
• src/Futhark/Optimise/Unstream.hs +41/−41
• src/Futhark/Pass.hs +13/−13
• src/Futhark/Pass/ExpandAllocations.hs +55/−55
• src/Futhark/Pass/ExplicitAllocations.hs +178/−175
• src/Futhark/Pass/ExplicitAllocations/GPU.hs +192/−0
• src/Futhark/Pass/ExplicitAllocations/Kernels.hs +0/−192
• src/Futhark/Pass/ExplicitAllocations/MC.hs +1/−1
• src/Futhark/Pass/ExplicitAllocations/SegOp.hs +16/−16
• src/Futhark/Pass/ExtractKernels.hs +47/−45
• src/Futhark/Pass/ExtractKernels/BlockedKernel.hs +56/−57
• src/Futhark/Pass/ExtractKernels/DistributeNests.hs +112/−112
• src/Futhark/Pass/ExtractKernels/Distribution.hs +21/−21
• src/Futhark/Pass/ExtractKernels/ISRWIM.hs +2/−2
• src/Futhark/Pass/ExtractKernels/Interchange.hs +14/−5
• src/Futhark/Pass/ExtractKernels/Intragroup.hs +24/−24
• src/Futhark/Pass/ExtractKernels/StreamKernel.hs +24/−24
• src/Futhark/Pass/ExtractKernels/ToGPU.hs +85/−0
• src/Futhark/Pass/ExtractKernels/ToKernels.hs +0/−85
• src/Futhark/Pass/ExtractMulticore.hs +1/−1
• src/Futhark/Pass/FirstOrderTransform.hs +2/−2
• src/Futhark/Pass/KernelBabysitting.hs +16/−16
• src/Futhark/Pass/Simplify.hs +10/−10
• src/Futhark/Passes.hs +19/−16
• src/Futhark/Pipeline.hs +19/−19
• src/Futhark/Script.hs +26/−44
• src/Futhark/Server.hs +0/−211
• src/Futhark/Test.hs +50/−63
• src/Futhark/Test/Values.hs +16/−815
• src/Futhark/Test/Values/Parser.hs +0/−167
• src/Futhark/Tools.hs +15/−15
• src/Futhark/Transform/CopyPropagate.hs +15/−15
• src/Futhark/Transform/FirstOrderTransform.hs +33/−33
• src/Futhark/Transform/Rename.hs +32/−32
• src/Futhark/Transform/Substitute.hs +18/−18
• src/Futhark/TypeCheck.hs +187/−187
• src/Futhark/Util.hs +14/−0
• src/Futhark/Util/Loc.hs +0/−2
• src/Futhark/Util/Pretty.hs +0/−1
• src/Language/Futhark/Core.hs +0/−15
• src/Language/Futhark/Syntax.hs +1/−0
• unittests/Futhark/IR/Syntax/CoreTests.hs +1/−1
• unittests/Futhark/Optimise/ReuseAllocations/GreedyColoringTests.hs +70/−0
• unittests/futhark_tests.hs +3/−1

@@ -301,6 +301,11 @@ be careful to check the return code of *both* the entry point itself, and :c:func:`futhark_context_sync`. +For the rules on entry points that consume their input, see+:ref:`api-consumption`.  Note that even if a value has been consumed,+you must still manually free it.  This is the only operation that is+permitted on a consumed value.+ GPU --- @@ -432,7 +437,6 @@    value less than ``1``, then the runtime system will use one thread    per detected core. - General guarantees ------------------ @@ -459,3 +463,8 @@ OpenCL) may perform file system operations during startup, and perhaps for caching GPU kernels in some cases.  This is beyond Futhark's control.++Violation the restrictions of consumption (see :ref:`api-consumption`)+can result in undefined behaviour.  This does not matter for programs+whose entry points do not have unique parameter types+(:ref:`in-place-updates`).

@@ -83,7 +83,7 @@ DIRECTIVES ========== -A directive is a way to show the result of running a funtion.+A directive is a way to show the result of running a function. Depending on the directive, this can be as simple as printing the textual representation of the result, or as complex as running an external plotting program and referencing a generated image.@@ -205,7 +205,7 @@ Note that empty arrays must be written using the ``empty(t)`` notation, e.g. ``empty([0]i32)``. -Function applications are either of Futhark funtions or *builtin+Function applications are either of Futhark functions or *builtin functions*.  The latter are prefixed with ``$`` and are magical (usually impure) functions that could not possibly be implemented in Futhark.  The following builtins are supported:

@@ -52,9 +52,20 @@ produce outputs of defined types.  The notion of transparent and opaque types are the same as in the C API: primitives and array of primitives are directly supported, and everything else is treated as-opaque.  See also :ref:`valuemapping`. When printed, types-follow basic Futhark type syntax *without* sizes (e.g. ``[][]i32``).+opaque.  See also :ref:`valuemapping`. When printed, types follow+basic Futhark type syntax *without* sizes (e.g. ``[][]i32``).+Uniqueness is not part of the types, but is indicated with an asterisk+in the ``inputs`` and ``outputs`` commands (see below). +Consumption and aliasing+------------------------++Since the server protocol closely models the C API, the same rules+apply to entry points that consume their arguments (see+:ref:`api-consumption`).  In particular, consumed variables must still+be freed with the ``free`` command - but this is the only operation+that may be used on consumed variables.+ Commands -------- @@ -92,13 +103,14 @@ ..................  Print the types of inputs accepted by the given entry point, one per-line.+line.  If the given input is consumed, the type is prefixed by `*`.  ``outputs`` *entry* ...................  Print the types of outputs produced by the given entry point, one per-line.+line.  If the given output is guaranteed to be unique (does not alias+any inputs), the type is prefixed by `*`.  ``clear`` .........

@@ -340,6 +340,38 @@   rule does not apply when the entry point has been given a return   type ascription that is not syntactically a tuple type. +.. _api-consumption:++Consumption and Aliasing+~~~~~~~~~~~~~~~~~~~~~~~~++Futhark's support for :ref:`in-place-updates` has implications for the+generated API.  Unfortunately, The type system of most languages+(e.g. C) is not rich enough to express the rules, so they are not+statically (or currently even dynamically checked).  Since Futhark+will never infer a unique/consuming type for an entry point parameter,+this section can be ignored unless uniqueness annotations have been+manually added to the entry points parameter types.  The rules are+essentially the same as in the language itself:++1. Each entry point input parameter is either *consuming* or+   *nonconsuming* (the default).  This corresponds to unique and+   nonunique types in the original Futhark program.  A value passed+   for a consuming parameter is considered *consumed*, now has an+   unspecified value, and may never be used again.  It must still be+   manually freed, if applicable.+   Further, any *aliases* of that value are also considered consumed+   and may not be used.++2. Each entry point output is either *unique* or *nonunique*.  A+   unique output has no aliases.  A nonunique output aliases *every*+   nonconsuming input parameter.++Note that these distinctions are currently usually not visible in the+generated API, and so correct usage requires knowledge of the original+types in the Futhark function.  The safest strategy is to not expose+unique types in entry points.+ Generating C ^^^^^^^^^^^^ 

@@ -1,7 +1,6 @@ cabal-version: 2.4--- Run 'cabal2nix . >futhark.nix' after adding deps. name:           futhark-version:        0.19.6+version:        0.19.7 synopsis:       An optimising compiler for a functional, array-oriented language.  description:    Futhark is a small programming language designed to be compiled to@@ -26,7 +25,7 @@                 .                 <<docs/assets/ohyes.png You too can go fast once you rewrite your program in Futhark.>> -category:       Language+category:       Futhark homepage:       https://futhark-lang.org bug-reports:    https://github.com/diku-dk/futhark/issues maintainer:     Troels Henriksen athas@sigkill.dk@@ -58,12 +57,14 @@       Futhark.Analysis.DataDependencies       Futhark.Analysis.HORep.MapNest       Futhark.Analysis.HORep.SOAC+      Futhark.Analysis.Interference+      Futhark.Analysis.LastUse       Futhark.Analysis.Metrics       Futhark.Analysis.Metrics.Type       Futhark.Analysis.PrimExp-      Futhark.Analysis.PrimExp.Parse       Futhark.Analysis.PrimExp.Convert       Futhark.Analysis.PrimExp.Generalize+      Futhark.Analysis.PrimExp.Parse       Futhark.Analysis.PrimExp.Simplify       Futhark.Analysis.Rephrase       Futhark.Analysis.SymbolTable@@ -97,8 +98,8 @@       Futhark.CodeGen.Backends.COpenCL.Boilerplate       Futhark.CodeGen.Backends.GenericC       Futhark.CodeGen.Backends.GenericC.CLI-      Futhark.CodeGen.Backends.GenericC.Server       Futhark.CodeGen.Backends.GenericC.Options+      Futhark.CodeGen.Backends.GenericC.Server       Futhark.CodeGen.Backends.GenericPython       Futhark.CodeGen.Backends.GenericPython.AST       Futhark.CodeGen.Backends.GenericPython.Definitions@@ -111,22 +112,22 @@       Futhark.CodeGen.Backends.SequentialPython       Futhark.CodeGen.Backends.SimpleRep       Futhark.CodeGen.ImpCode-      Futhark.CodeGen.ImpCode.Kernels+      Futhark.CodeGen.ImpCode.GPU       Futhark.CodeGen.ImpCode.Multicore       Futhark.CodeGen.ImpCode.OpenCL       Futhark.CodeGen.ImpCode.Sequential       Futhark.CodeGen.ImpGen       Futhark.CodeGen.ImpGen.CUDA-      Futhark.CodeGen.ImpGen.Kernels-      Futhark.CodeGen.ImpGen.Kernels.Base-      Futhark.CodeGen.ImpGen.Kernels.SegHist-      Futhark.CodeGen.ImpGen.Kernels.SegMap-      Futhark.CodeGen.ImpGen.Kernels.SegRed-      Futhark.CodeGen.ImpGen.Kernels.SegScan-      Futhark.CodeGen.ImpGen.Kernels.SegScan.SinglePass-      Futhark.CodeGen.ImpGen.Kernels.SegScan.TwoPass-      Futhark.CodeGen.ImpGen.Kernels.ToOpenCL-      Futhark.CodeGen.ImpGen.Kernels.Transpose+      Futhark.CodeGen.ImpGen.GPU+      Futhark.CodeGen.ImpGen.GPU.Base+      Futhark.CodeGen.ImpGen.GPU.SegHist+      Futhark.CodeGen.ImpGen.GPU.SegMap+      Futhark.CodeGen.ImpGen.GPU.SegRed+      Futhark.CodeGen.ImpGen.GPU.SegScan+      Futhark.CodeGen.ImpGen.GPU.SegScan.SinglePass+      Futhark.CodeGen.ImpGen.GPU.SegScan.TwoPass+      Futhark.CodeGen.ImpGen.GPU.ToOpenCL+      Futhark.CodeGen.ImpGen.GPU.Transpose       Futhark.CodeGen.ImpGen.Multicore       Futhark.CodeGen.ImpGen.Multicore.Base       Futhark.CodeGen.ImpGen.Multicore.SegHist@@ -148,19 +149,18 @@       Futhark.FreshNames       Futhark.IR       Futhark.IR.Aliases-      Futhark.IR.Decorations-      Futhark.IR.Parse-      Futhark.IR.Kernels-      Futhark.IR.Kernels.Kernel-      Futhark.IR.Kernels.Simplify-      Futhark.IR.Kernels.Sizes-      Futhark.IR.KernelsMem+      Futhark.IR.GPU+      Futhark.IR.GPU.Kernel+      Futhark.IR.GPU.Simplify+      Futhark.IR.GPU.Sizes+      Futhark.IR.GPUMem       Futhark.IR.MC       Futhark.IR.MC.Op       Futhark.IR.MCMem       Futhark.IR.Mem       Futhark.IR.Mem.IxFun       Futhark.IR.Mem.Simplify+      Futhark.IR.Parse       Futhark.IR.Pretty       Futhark.IR.Primitive       Futhark.IR.Primitive.Parse@@ -174,6 +174,7 @@       Futhark.IR.Prop.Scope       Futhark.IR.Prop.TypeOf       Futhark.IR.Prop.Types+      Futhark.IR.Rep       Futhark.IR.RetType       Futhark.IR.SOACS       Futhark.IR.SOACS.SOAC@@ -207,9 +208,11 @@       Futhark.Optimise.InPlaceLowering.LowerIntoStm       Futhark.Optimise.InPlaceLowering.SubstituteIndices       Futhark.Optimise.InliningDeadFun+      Futhark.Optimise.ReuseAllocations+      Futhark.Optimise.ReuseAllocations.GreedyColoring       Futhark.Optimise.Simplify       Futhark.Optimise.Simplify.Engine-      Futhark.Optimise.Simplify.Lore+      Futhark.Optimise.Simplify.Rep       Futhark.Optimise.Simplify.Rule       Futhark.Optimise.Simplify.Rules       Futhark.Optimise.Simplify.Rules.BasicOp@@ -224,10 +227,10 @@       Futhark.Pass       Futhark.Pass.ExpandAllocations       Futhark.Pass.ExplicitAllocations-      Futhark.Pass.ExplicitAllocations.Kernels+      Futhark.Pass.ExplicitAllocations.GPU+      Futhark.Pass.ExplicitAllocations.MC       Futhark.Pass.ExplicitAllocations.SegOp       Futhark.Pass.ExplicitAllocations.Seq-      Futhark.Pass.ExplicitAllocations.MC       Futhark.Pass.ExtractKernels       Futhark.Pass.ExtractKernels.BlockedKernel       Futhark.Pass.ExtractKernels.DistributeNests@@ -236,7 +239,7 @@       Futhark.Pass.ExtractKernels.Interchange       Futhark.Pass.ExtractKernels.Intragroup       Futhark.Pass.ExtractKernels.StreamKernel-      Futhark.Pass.ExtractKernels.ToKernels+      Futhark.Pass.ExtractKernels.ToGPU       Futhark.Pass.ExtractMulticore       Futhark.Pass.FirstOrderTransform       Futhark.Pass.KernelBabysitting@@ -247,10 +250,8 @@       Futhark.Pkg.Solve       Futhark.Pkg.Types       Futhark.Script-      Futhark.Server       Futhark.Test       Futhark.Test.Values-      Futhark.Test.Values.Parser       Futhark.Tools       Futhark.Transform.CopyPropagate       Futhark.Transform.FirstOrderTransform@@ -314,6 +315,8 @@     , file-embed >=0.0.9     , filepath >=1.4.1.1     , free >=4.12.4+    , futhark-data >= 1.0.0.1+    , futhark-server >= 1.1.0.0     , gitrev >=1.2.0     , hashable     , haskeline@@ -372,6 +375,7 @@       Futhark.IR.PrimitiveTests       Language.Futhark.CoreTests       Language.Futhark.SyntaxTests+      Futhark.Optimise.ReuseAllocations.GreedyColoringTests       Paths_futhark   hs-source-dirs:       unittests

@@ -131,7 +131,9 @@   const char *name;   entry_point_fn f;   struct type **out_types;+  bool *out_unique;   struct type **in_types;+  bool *in_unique; };  int entry_num_ins(struct entry_point *e) {@@ -459,6 +461,9 @@    int num_ins = entry_num_ins(e);   for (int i = 0; i < num_ins; i++) {+    if (e->in_unique[i]) {+      putchar('*');+    }     puts(e->in_types[i]->name);   } }@@ -475,6 +480,9 @@    int num_outs = entry_num_outs(e);   for (int i = 0; i < num_outs; i++) {+    if (e->out_unique[i]) {+      putchar('*');+    }     puts(e->out_types[i]->name);   } }

@@ -29,12 +29,12 @@ import qualified Futhark.CodeGen.Backends.PyOpenCL as PyOpenCL import qualified Futhark.CodeGen.Backends.SequentialC as SequentialC import qualified Futhark.CodeGen.Backends.SequentialPython as SequentialPy-import qualified Futhark.CodeGen.ImpGen.Kernels as ImpGenKernels+import qualified Futhark.CodeGen.ImpGen.GPU as ImpGenGPU import qualified Futhark.CodeGen.ImpGen.Multicore as ImpGenMulticore import qualified Futhark.CodeGen.ImpGen.Sequential as ImpGenSequential import Futhark.Compiler.CLI import Futhark.IR-import Futhark.IR.KernelsMem (KernelsMem)+import Futhark.IR.GPUMem (GPUMem) import Futhark.IR.MCMem (MCMem) import Futhark.IR.Prop.Aliases import Futhark.IR.SeqMem (SeqMem)@@ -46,7 +46,7 @@ import qualified System.Info  -- | Print the result to stdout.-printAction :: ASTLore lore => Action lore+printAction :: ASTRep rep => Action rep printAction =   Action     { actionName = "Prettyprint",@@ -55,7 +55,7 @@     }  -- | Print the result to stdout, alias annotations.-printAliasesAction :: (ASTLore lore, CanBeAliased (Op lore)) => Action lore+printAliasesAction :: (ASTRep rep, CanBeAliased (Op rep)) => Action rep printAliasesAction =   Action     { actionName = "Prettyprint",@@ -64,7 +64,7 @@     }  -- | Print metrics about AST node counts to stdout.-metricsAction :: OpMetrics (Op lore) => Action lore+metricsAction :: OpMetrics (Op rep) => Action rep metricsAction =   Action     { actionName = "Compute metrics",@@ -82,12 +82,12 @@     }  -- | Convert the program to GPU ImpCode and print it to stdout.-kernelImpCodeGenAction :: Action KernelsMem+kernelImpCodeGenAction :: Action GPUMem kernelImpCodeGenAction =   Action     { actionName = "Compile imperative kernels",       actionDescription = "Translate program into imperative IL with kernels and write it on standard output.",-      actionProcedure = liftIO . putStrLn . pretty . snd <=< ImpGenKernels.compileProgOpenCL+      actionProcedure = liftIO . putStrLn . pretty . snd <=< ImpGenGPU.compileProgOpenCL     }  -- | Convert the program to CPU multicore ImpCode and print it to stdout.@@ -173,7 +173,7 @@           runCC cpath outpath ["-O3", "-std=c99"] ["-lm"]  -- | The @futhark opencl@ action.-compileOpenCLAction :: FutharkConfig -> CompilerMode -> FilePath -> Action KernelsMem+compileOpenCLAction :: FutharkConfig -> CompilerMode -> FilePath -> Action GPUMem compileOpenCLAction fcfg mode outpath =   Action     { actionName = "Compile to OpenCL",@@ -206,7 +206,7 @@           runCC cpath outpath ["-O", "-std=c99"] ("-lm" : extra_options)  -- | The @futhark cuda@ action.-compileCUDAAction :: FutharkConfig -> CompilerMode -> FilePath -> Action KernelsMem+compileCUDAAction :: FutharkConfig -> CompilerMode -> FilePath -> Action GPUMem compileCUDAAction fcfg mode outpath =   Action     { actionName = "Compile to CUDA",@@ -291,7 +291,7 @@       actionProcedure = pythonCommon SequentialPy.compileProg fcfg mode outpath     } -compilePyOpenCLAction :: FutharkConfig -> CompilerMode -> FilePath -> Action KernelsMem+compilePyOpenCLAction :: FutharkConfig -> CompilerMode -> FilePath -> Action GPUMem compilePyOpenCLAction fcfg mode outpath =   Action     { actionName = "Compile to PyOpenCL",

@@ -1,7 +1,7 @@ {-# LANGUAGE FlexibleContexts #-}  -- | Alias analysis of a full Futhark program.  Takes as input a--- program with an arbitrary lore and produces one with aliases.  This+-- program with an arbitrary rep and produces one with aliases.  This -- module does not implement the aliasing logic itself, and derives -- its information from definitions in -- "Futhark.IR.Prop.Aliases" and@@ -26,37 +26,37 @@  -- | Perform alias analysis on a Futhark program. aliasAnalysis ::-  (ASTLore lore, CanBeAliased (Op lore)) =>-  Prog lore ->-  Prog (Aliases lore)+  (ASTRep rep, CanBeAliased (Op rep)) =>+  Prog rep ->+  Prog (Aliases rep) aliasAnalysis (Prog consts funs) =   Prog (fst (analyseStms mempty consts)) (map analyseFun funs)  analyseFun ::-  (ASTLore lore, CanBeAliased (Op lore)) =>-  FunDef lore ->-  FunDef (Aliases lore)+  (ASTRep rep, CanBeAliased (Op rep)) =>+  FunDef rep ->+  FunDef (Aliases rep) analyseFun (FunDef entry attrs fname restype params body) =   FunDef entry attrs fname restype params body'   where     body' = analyseBody mempty body  analyseBody ::-  ( ASTLore lore,-    CanBeAliased (Op lore)+  ( ASTRep rep,+    CanBeAliased (Op rep)   ) =>   AliasTable ->-  Body lore ->-  Body (Aliases lore)-analyseBody atable (Body lore stms result) =+  Body rep ->+  Body (Aliases rep)+analyseBody atable (Body rep stms result) =   let (stms', _atable') = analyseStms atable stms-   in mkAliasedBody lore stms' result+   in mkAliasedBody rep stms' result  analyseStms ::-  (ASTLore lore, CanBeAliased (Op lore)) =>+  (ASTRep rep, CanBeAliased (Op rep)) =>   AliasTable ->-  Stms lore ->-  (Stms (Aliases lore), AliasesAndConsumed)+  Stms rep ->+  (Stms (Aliases rep), AliasesAndConsumed) analyseStms orig_aliases =   foldl' f (mempty, (orig_aliases, mempty)) . stmsToList   where@@ -66,21 +66,21 @@        in (stms <> oneStm stm', atable')  analyseStm ::-  (ASTLore lore, CanBeAliased (Op lore)) =>+  (ASTRep rep, CanBeAliased (Op rep)) =>   AliasTable ->-  Stm lore ->-  Stm (Aliases lore)+  Stm rep ->+  Stm (Aliases rep) analyseStm aliases (Let pat (StmAux cs attrs dec) e) =   let e' = analyseExp aliases e       pat' = addAliasesToPattern pat e'-      lore' = (AliasDec $ consumedInExp e', dec)-   in Let pat' (StmAux cs attrs lore') e'+      rep' = (AliasDec $ consumedInExp e', dec)+   in Let pat' (StmAux cs attrs rep') e'  analyseExp ::-  (ASTLore lore, CanBeAliased (Op lore)) =>+  (ASTRep rep, CanBeAliased (Op rep)) =>   AliasTable ->-  Exp lore ->-  Exp (Aliases lore)+  Exp rep ->+  Exp (Aliases rep) -- Would be better to put this in a BranchType annotation, but that -- requires a lot of other work. analyseExp aliases (If cond tb fb dec) =@@ -115,10 +115,10 @@         }  analyseLambda ::-  (ASTLore lore, CanBeAliased (Op lore)) =>+  (ASTRep rep, CanBeAliased (Op rep)) =>   AliasTable ->-  Lambda lore ->-  Lambda (Aliases lore)+  Lambda rep ->+  Lambda (Aliases rep) analyseLambda aliases lam =   let body = analyseBody aliases $ lambdaBody lam    in lam

@@ -18,13 +18,13 @@ type Dependencies = M.Map VName Names  -- | Compute the data dependencies for an entire body.-dataDependencies :: ASTLore lore => Body lore -> Dependencies+dataDependencies :: ASTRep rep => Body rep -> Dependencies dataDependencies = dataDependencies' M.empty  dataDependencies' ::-  ASTLore lore =>+  ASTRep rep =>   Dependencies ->-  Body lore ->+  Body rep ->   Dependencies dataDependencies' startdeps = foldl grow startdeps . bodyStms   where

@@ -24,7 +24,7 @@ import qualified Futhark.IR.SOACS.SOAC as Futhark import Futhark.Transform.Substitute -data Nesting lore = Nesting+data Nesting rep = Nesting   { nestingParamNames :: [VName],     nestingResult :: [VName],     nestingReturnType :: [Type],@@ -32,25 +32,25 @@   }   deriving (Eq, Ord, Show) -data MapNest lore = MapNest SubExp (Lambda lore) [Nesting lore] [SOAC.Input]+data MapNest rep = MapNest SubExp (Lambda rep) [Nesting rep] [SOAC.Input]   deriving (Show) -typeOf :: MapNest lore -> [Type]+typeOf :: MapNest rep -> [Type] typeOf (MapNest w lam [] _) =   map (`arrayOfRow` w) $ lambdaReturnType lam typeOf (MapNest w _ (nest : _) _) =   map (`arrayOfRow` w) $ nestingReturnType nest -params :: MapNest lore -> [VName]+params :: MapNest rep -> [VName] params (MapNest _ lam [] _) =   map paramName $ lambdaParams lam params (MapNest _ _ (nest : _) _) =   nestingParamNames nest -inputs :: MapNest lore -> [SOAC.Input]+inputs :: MapNest rep -> [SOAC.Input] inputs (MapNest _ _ _ inps) = inps -setInputs :: [SOAC.Input] -> MapNest lore -> MapNest lore+setInputs :: [SOAC.Input] -> MapNest rep -> MapNest rep setInputs [] (MapNest w body ns _) = MapNest w body ns [] setInputs (inp : inps) (MapNest _ body ns _) = MapNest w body ns' (inp : inps)   where@@ -60,24 +60,24 @@     setDepth n nw = n {nestingWidth = nw}  fromSOAC ::-  ( Bindable lore,+  ( Bindable rep,     MonadFreshNames m,-    LocalScope lore m,-    Op lore ~ Futhark.SOAC lore+    LocalScope rep m,+    Op rep ~ Futhark.SOAC rep   ) =>-  SOAC lore ->-  m (Maybe (MapNest lore))+  SOAC rep ->+  m (Maybe (MapNest rep)) fromSOAC = fromSOAC' mempty  fromSOAC' ::-  ( Bindable lore,+  ( Bindable rep,     MonadFreshNames m,-    LocalScope lore m,-    Op lore ~ Futhark.SOAC lore+    LocalScope rep m,+    Op rep ~ Futhark.SOAC rep   ) =>   [Ident] ->-  SOAC lore ->-  m (Maybe (MapNest lore))+  SOAC rep ->+  m (Maybe (MapNest rep)) fromSOAC' bound (SOAC.Screma w (SOAC.ScremaForm [] [] lam) inps) = do   maybenest <- case ( stmsToList $ bodyStms $ lambdaBody lam,                       bodyResult $ lambdaBody lam@@ -142,13 +142,13 @@  toSOAC ::   ( MonadFreshNames m,-    HasScope lore m,-    Bindable lore,-    BinderOps lore,-    Op lore ~ Futhark.SOAC lore+    HasScope rep m,+    Bindable rep,+    BinderOps rep,+    Op rep ~ Futhark.SOAC rep   ) =>-  MapNest lore ->-  m (SOAC lore)+  MapNest rep ->+  m (SOAC rep) toSOAC (MapNest w lam [] inps) =   return $ SOAC.Screma w (Futhark.mapSOAC lam) inps toSOAC (MapNest w lam (Nesting npnames nres nrettype nw : ns) inps) = do

@@ -226,7 +226,7 @@ -- an input transformation of an array variable.  If so, return the -- variable and the transformation.  Only 'Rearrange' and 'Reshape' -- are possible to express this way.-transformFromExp :: Certificates -> Exp lore -> Maybe (VName, ArrayTransform)+transformFromExp :: Certificates -> Exp rep -> Maybe (VName, ArrayTransform) transformFromExp cs (BasicOp (Futhark.Rearrange perm v)) =   Just (v, Rearrange cs perm) transformFromExp cs (BasicOp (Futhark.Reshape shape v)) =@@ -374,11 +374,11 @@   addTransform (Rearrange mempty $ transposeIndex k n [0 .. inputRank inp -1]) inp  -- | A definite representation of a SOAC expression.-data SOAC lore-  = Stream SubExp (StreamForm lore) (Lambda lore) [SubExp] [Input]-  | Scatter SubExp (Lambda lore) [Input] [(Shape, Int, VName)]-  | Screma SubExp (ScremaForm lore) [Input]-  | Hist SubExp [HistOp lore] (Lambda lore) [Input]+data SOAC rep+  = Stream SubExp (StreamForm rep) (Lambda rep) [SubExp] [Input]+  | Scatter SubExp (Lambda rep) [Input] [(Shape, Int, VName)]+  | Screma SubExp (ScremaForm rep) [Input]+  | Hist SubExp [HistOp rep] (Lambda rep) [Input]   deriving (Eq, Show)  instance PP.Pretty Input where@@ -395,21 +395,21 @@       f e (Replicate cs ne) =         text "replicate" <> ppr cs <> PP.apply [ppr ne, e] -instance PrettyLore lore => PP.Pretty (SOAC lore) where+instance PrettyRep rep => PP.Pretty (SOAC rep) where   ppr (Screma w form arrs) = Futhark.ppScrema w arrs form   ppr (Hist len ops bucket_fun imgs) =     Futhark.ppHist len ops bucket_fun imgs   ppr soac = text $ show soac  -- | Returns the inputs used in a SOAC.-inputs :: SOAC lore -> [Input]+inputs :: SOAC rep -> [Input] inputs (Stream _ _ _ _ arrs) = arrs inputs (Scatter _len _lam ivs _as) = ivs inputs (Screma _ _ arrs) = arrs inputs (Hist _ _ _ inps) = inps  -- | Set the inputs to a SOAC.-setInputs :: [Input] -> SOAC lore -> SOAC lore+setInputs :: [Input] -> SOAC rep -> SOAC rep setInputs arrs (Stream w form lam nes _) =   Stream (newWidth arrs w) form lam nes arrs setInputs arrs (Scatter w lam _ivs as) =@@ -424,14 +424,14 @@ newWidth (inp : _) _ = arraySize 0 $ inputType inp  -- | The lambda used in a given SOAC.-lambda :: SOAC lore -> Lambda lore+lambda :: SOAC rep -> Lambda rep lambda (Stream _ _ lam _ _) = lam lambda (Scatter _len lam _ivs _as) = lam lambda (Screma _ (ScremaForm _ _ lam) _) = lam lambda (Hist _ _ lam _) = lam  -- | Set the lambda used in the SOAC.-setLambda :: Lambda lore -> SOAC lore -> SOAC lore+setLambda :: Lambda rep -> SOAC rep -> SOAC rep setLambda lam (Stream w form _ nes arrs) =   Stream w form lam nes arrs setLambda lam (Scatter len _lam ivs as) =@@ -442,7 +442,7 @@   Hist w ops lam inps  -- | The return type of a SOAC.-typeOf :: SOAC lore -> [Type]+typeOf :: SOAC rep -> [Type] typeOf (Stream w _ lam nes _) =   let accrtps = take (length nes) $ lambdaReturnType lam       arrtps =@@ -464,7 +464,7 @@  -- | The "width" of a SOAC is the expected outer size of its array -- inputs _after_ input-transforms have been carried out.-width :: SOAC lore -> SubExp+width :: SOAC rep -> SubExp width (Stream w _ _ _ _) = w width (Scatter len _lam _ivs _as) = len width (Screma w _ _) = w@@ -472,16 +472,16 @@  -- | Convert a SOAC to the corresponding expression. toExp ::-  (MonadBinder m, Op (Lore m) ~ Futhark.SOAC (Lore m)) =>-  SOAC (Lore m) ->-  m (Exp (Lore m))+  (MonadBinder m, Op (Rep m) ~ Futhark.SOAC (Rep m)) =>+  SOAC (Rep m) ->+  m (Exp (Rep m)) toExp soac = Op <$> toSOAC soac  -- | Convert a SOAC to a Futhark-level SOAC. toSOAC ::   MonadBinder m =>-  SOAC (Lore m) ->-  m (Futhark.SOAC (Lore m))+  SOAC (Rep m) ->+  m (Futhark.SOAC (Rep m)) toSOAC (Stream w form lam nes inps) =   Futhark.Stream w <$> inputsToSubExps inps <*> pure form <*> pure nes <*> pure lam toSOAC (Scatter len lam ivs dests) = do@@ -503,9 +503,9 @@ -- representation, or a reason why the expression does not have the -- valid form. fromExp ::-  (Op lore ~ Futhark.SOAC lore, HasScope lore m) =>-  Exp lore ->-  m (Either NotSOAC (SOAC lore))+  (Op rep ~ Futhark.SOAC rep, HasScope rep m) =>+  Exp rep ->+  m (Either NotSOAC (SOAC rep)) fromExp (Op (Futhark.Stream w as form nes lam)) =   Right . Stream w form lam nes <$> traverse varInput as fromExp (Op (Futhark.Scatter len lam ivs as)) =@@ -520,9 +520,9 @@ --   Returns the Stream SOAC and the --   extra-accumulator body-result ident if any. soacToStream ::-  (MonadFreshNames m, Bindable lore, Op lore ~ Futhark.SOAC lore) =>-  SOAC lore ->-  m (SOAC lore, [Ident])+  (MonadFreshNames m, Bindable rep, Op rep ~ Futhark.SOAC rep) =>+  SOAC rep ->+  m (SOAC rep, [Ident]) soacToStream soac = do   chunk_param <- newParam "chunk" $ Prim int64   let chvar = Futhark.Var $ paramName chunk_param@@ -690,10 +690,10 @@     _ -> return (soac, [])   where     mkMapPlusAccLam ::-      (MonadFreshNames m, Bindable lore) =>+      (MonadFreshNames m, Bindable rep) =>       [SubExp] ->-      Lambda lore ->-      m (Lambda lore)+      Lambda rep ->+      m (Lambda rep)     mkMapPlusAccLam accs plus = do       let (accpars, rempars) = splitAt (length accs) $ lambdaParams plus           parbnds =@@ -715,10 +715,10 @@       renameLambda $ Lambda rempars newlambdy $ lambdaReturnType plus      mkPlusBnds ::-      (MonadFreshNames m, Bindable lore) =>-      Lambda lore ->+      (MonadFreshNames m, Bindable rep) =>+      Lambda rep ->       [SubExp] ->-      m (Body lore)+      m (Body rep)     mkPlusBnds plus accels = do       plus' <- renameLambda plus       let parbnds =

@@ -0,0 +1,326 @@+{-# LANGUAGE ConstraintKinds #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE TypeFamilies #-}++-- | Interference analysis for Futhark programs.+module Futhark.Analysis.Interference (Graph, analyseGPU) where++import Control.Monad.Reader+import Data.Foldable (toList)+import Data.Function ((&))+import Data.Functor ((<&>))+import Data.Map (Map)+import qualified Data.Map as M+import Data.Maybe (catMaybes, fromMaybe)+import Data.Set (Set)+import qualified Data.Set as S+import Futhark.Analysis.LastUse (LastUseMap)+import Futhark.IR.GPUMem+import Futhark.Util (invertMap)++-- | The set of `VName` currently in use.+type InUse = Names++-- | The set of `VName` that are no longer in use.+type LastUsed = Names++-- | An interference graph. An element `(x, y)` in the set means that there is+-- an undirected edge between `x` and `y`, and therefore the lifetimes of `x`+-- and `y` overlap and they "interfere" with each other. We assume that pairs+-- are always normalized, such that `x` < `y`, before inserting. This should+-- prevent any duplicates. We also don't allow any pairs where `x == y`.+type Graph a = Set (a, a)++-- | Insert an edge between two values into the graph.+makeEdge :: Ord a => a -> a -> Graph a+makeEdge v1 v2+  | v1 == v2 = mempty+  | otherwise = S.singleton (min v1 v2, max v1 v2)++-- | Compute the cartesian product of two foldable collections, using the given+-- combinator function.+cartesian :: (Monoid m, Foldable t) => (a -> a -> m) -> t a -> t a -> m+cartesian f xs ys =+  [(x, y) | x <- toList xs, y <- toList ys]+    & foldMap (uncurry f)++analyseStm ::+  LocalScope GPUMem m =>+  LastUseMap ->+  InUse ->+  Stm GPUMem ->+  m (InUse, LastUsed, Graph VName)+analyseStm lumap inuse0 stm =+  inScopeOf stm $ do+    let pat_name = patElemName $ head $ patternValueElements $ stmPattern stm++    new_mems <-+      stmPattern stm+        & patternValueElements+        & mapM (memInfo . patElemName)+        <&> catMaybes+        <&> namesFromList++    -- `new_mems` should interfere with any mems inside the statement expression+    let inuse_outside = inuse0 <> new_mems++    -- `inuse` is the set of memory blocks that are inuse at the end of any code+    -- bodies inside the expression. `lus` is the set of all memory blocks that+    -- have reached their last use in any code bodies inside the+    -- expression. `graph` is the interference graph computed for any code+    -- bodies inside the expression.+    (inuse, lus, graph) <- analyseExp lumap inuse_outside (stmExp stm)++    last_use_mems <-+      M.lookup pat_name lumap+        & fromMaybe mempty+        & namesToList+        & mapM memInfo+        <&> catMaybes+        <&> namesFromList+        <&> namesIntersection inuse_outside++    return+      ( (inuse_outside `namesSubtract` last_use_mems `namesSubtract` lus)+          <> new_mems,+        (lus <> last_use_mems) `namesSubtract` new_mems,+        graph+          <> cartesian+            makeEdge+            (namesToList inuse_outside)+            (namesToList $ inuse_outside <> inuse <> lus <> last_use_mems)+      )++analyseExp ::+  LocalScope GPUMem m =>+  LastUseMap ->+  InUse ->+  Exp GPUMem ->+  m (InUse, LastUsed, Graph VName)+analyseExp lumap inuse_outside expr =+  case expr of+    If _ then_body else_body _ -> do+      res1 <- analyseBody lumap inuse_outside then_body+      res2 <- analyseBody lumap inuse_outside else_body+      return $ res1 <> res2+    DoLoop _ _ _ body -> do+      analyseBody lumap inuse_outside body+    Op (Inner (SegOp segop)) -> do+      analyseSegOp lumap inuse_outside segop+    _ ->+      return mempty++analyseKernelBody ::+  LocalScope GPUMem m =>+  LastUseMap ->+  InUse ->+  KernelBody GPUMem ->+  m (InUse, LastUsed, Graph VName)+analyseKernelBody lumap inuse body = analyseStms lumap inuse $ kernelBodyStms body++analyseBody ::+  LocalScope GPUMem m =>+  LastUseMap ->+  InUse ->+  Body GPUMem ->+  m (InUse, LastUsed, Graph VName)+analyseBody lumap inuse body = analyseStms lumap inuse $ bodyStms body++analyseStms ::+  LocalScope GPUMem m =>+  LastUseMap ->+  InUse ->+  Stms GPUMem ->+  m (InUse, LastUsed, Graph VName)+analyseStms lumap inuse0 stms = do+  inScopeOf stms $ foldM helper (inuse0, mempty, mempty) $ stmsToList stms+  where+    helper (inuse, lus, graph) stm = do+      (inuse', lus', graph') <- analyseStm lumap inuse stm+      return (inuse', lus' <> lus, graph' <> graph)++analyseSegOp ::+  LocalScope GPUMem m =>+  LastUseMap ->+  InUse ->+  SegOp lvl GPUMem ->+  m (InUse, LastUsed, Graph VName)+analyseSegOp lumap inuse (SegMap _ _ _ body) =+  analyseKernelBody lumap inuse body+analyseSegOp lumap inuse (SegRed _ _ binops _ body) =+  segWithBinOps lumap inuse binops body+analyseSegOp lumap inuse (SegScan _ _ binops _ body) = do+  segWithBinOps lumap inuse binops body+analyseSegOp lumap inuse (SegHist _ _ histops _ body) = do+  (inuse', lus', graph) <- analyseKernelBody lumap inuse body+  (inuse'', lus'', graph') <- mconcat <$> mapM (analyseHistOp lumap inuse') histops+  return (inuse'', lus' <> lus'', graph <> graph')++segWithBinOps ::+  LocalScope GPUMem m =>+  LastUseMap ->+  InUse ->+  [SegBinOp GPUMem] ->+  KernelBody GPUMem ->+  m (InUse, LastUsed, Graph VName)+segWithBinOps lumap inuse binops body = do+  (inuse', lus', graph) <- analyseKernelBody lumap inuse body+  (inuse'', lus'', graph') <-+    mconcat+      <$> mapM+        (analyseSegBinOp lumap inuse')+        binops+  return (inuse'', lus' <> lus'', graph <> graph')++analyseSegBinOp ::+  LocalScope GPUMem m =>+  LastUseMap ->+  InUse ->+  SegBinOp GPUMem ->+  m (InUse, LastUsed, Graph VName)+analyseSegBinOp lumap inuse (SegBinOp _ lambda _ _) =+  analyseLambda lumap inuse lambda++analyseHistOp ::+  LocalScope GPUMem m =>+  LastUseMap ->+  InUse ->+  HistOp GPUMem ->+  m (InUse, LastUsed, Graph VName)+analyseHistOp lumap inuse histop =+  analyseLambda lumap inuse (histOp histop)++analyseLambda ::+  LocalScope GPUMem m =>+  LastUseMap ->+  InUse ->+  Lambda GPUMem ->+  m (InUse, LastUsed, Graph VName)+analyseLambda lumap inuse (Lambda _ body _) =+  analyseBody lumap inuse body++-- | Perform interference analysis on the given statements. The result is a+-- triple of the names currently in use, names that hit their last use somewhere+-- within, and the resulting graph.+analyseGPU ::+  LocalScope GPUMem m =>+  LastUseMap ->+  Stms GPUMem ->+  m (Graph VName)+analyseGPU lumap stms = do+  (_, _, graph) <- analyseGPU' lumap stms+  -- We need to insert edges between memory blocks which differ in size, if they+  -- are in DefaultSpace. The problem is that during memory expansion,+  -- DefaultSpace arrays in kernels are interleaved. If the element sizes of two+  -- merged memory blocks are different, threads might try to read and write to+  -- overlapping memory positions. More information here:+  -- https://munksgaard.me/technical-diary/2020-12-30.html#org210775b+  spaces <- M.filter (== DefaultSpace) <$> memSpaces stms+  inv_size_map <-+    memSizes stms+      <&> flip M.restrictKeys (S.fromList $ M.keys spaces)+      <&> invertMap+  let new_edges =+        cartesian+          (\x y -> if x /= y then cartesian makeEdge x y else mempty)+          inv_size_map+          inv_size_map+  return $ graph <> new_edges++-- | Return a mapping from memory blocks to their element sizes in the given+-- statements.+memSizes :: LocalScope GPUMem m => Stms GPUMem -> m (Map VName Int)+memSizes stms =+  inScopeOf stms $ fmap mconcat <$> mapM memSizesStm $ stmsToList stms+  where+    memSizesStm :: LocalScope GPUMem m => Stm GPUMem -> m (Map VName Int)+    memSizesStm (Let pat _ e) = do+      arraySizes <- fmap mconcat <$> mapM memElemSize $ patternNames pat+      arraySizes' <- memSizesExp e+      return $ arraySizes <> arraySizes'+    memSizesExp :: LocalScope GPUMem m => Exp GPUMem -> m (Map VName Int)+    memSizesExp (Op (Inner (SegOp segop))) =+      let body = segBody segop+       in inScopeOf (kernelBodyStms body) $+            fmap mconcat+              <$> mapM memSizesStm+              $ stmsToList $ kernelBodyStms body+    memSizesExp (If _ then_body else_body _) = do+      then_res <- memSizes $ bodyStms then_body+      else_res <- memSizes $ bodyStms else_body+      return $ then_res <> else_res+    memSizesExp (DoLoop _ _ _ body) =+      memSizes $ bodyStms body+    memSizesExp _ = return mempty++-- | Return a mapping from memory blocks to the space they are allocated in.+memSpaces :: LocalScope GPUMem m => Stms GPUMem -> m (Map VName Space)+memSpaces stms =+  return $ foldMap getSpacesStm stms+  where+    getSpacesStm :: Stm GPUMem -> Map VName Space+    getSpacesStm (Let (Pattern [] [PatElem name _]) _ (Op (Alloc _ sp))) =+      M.singleton name sp+    getSpacesStm (Let _ _ (Op (Alloc _ _))) = error "impossible"+    getSpacesStm (Let _ _ (Op (Inner (SegOp segop)))) =+      foldMap getSpacesStm $ kernelBodyStms $ segBody segop+    getSpacesStm (Let _ _ (If _ then_body else_body _)) =+      foldMap getSpacesStm (bodyStms then_body)+        <> foldMap getSpacesStm (bodyStms else_body)+    getSpacesStm (Let _ _ (DoLoop _ _ _ body)) =+      foldMap getSpacesStm (bodyStms body)+    getSpacesStm _ = mempty++analyseGPU' ::+  LocalScope GPUMem m =>+  LastUseMap ->+  Stms GPUMem ->+  m (InUse, LastUsed, Graph VName)+analyseGPU' lumap stms =+  mconcat . toList <$> mapM helper stms+  where+    helper ::+      LocalScope GPUMem m =>+      Stm GPUMem ->+      m (InUse, LastUsed, Graph VName)+    helper stm@Let {stmExp = Op (Inner (SegOp segop))} =+      inScopeOf stm $ analyseSegOp lumap mempty segop+    helper stm@Let {stmExp = If _ then_body else_body _} =+      inScopeOf stm $ do+        res1 <- analyseGPU' lumap (bodyStms then_body)+        res2 <- analyseGPU' lumap (bodyStms else_body)+        return (res1 <> res2)+    helper stm@Let {stmExp = DoLoop _ _ _ body} =+      inScopeOf stm $+        analyseGPU' lumap $ bodyStms body+    helper stm =+      inScopeOf stm $ return mempty++nameInfoToMemInfo :: Mem rep => NameInfo rep -> MemBound NoUniqueness+nameInfoToMemInfo info =+  case info of+    FParamName summary -> noUniquenessReturns summary+    LParamName summary -> summary+    LetName summary -> summary+    IndexName it -> MemPrim $ IntType it++memInfo :: LocalScope GPUMem m => VName -> m (Maybe VName)+memInfo vname = do+  summary <- asksScope (fmap nameInfoToMemInfo . M.lookup vname)+  case summary of+    Just (MemArray _ _ _ (ArrayIn mem _)) ->+      return $ Just mem+    _ ->+      return Nothing++-- | Returns a mapping from memory block to element size. The input is the+-- `VName` of a variable (supposedly an array), and the result is a mapping from+-- the memory block of that array to element size of the array.+memElemSize :: LocalScope GPUMem m => VName -> m (Map VName Int)+memElemSize vname = do+  summary <- asksScope (fmap nameInfoToMemInfo . M.lookup vname)+  case summary of+    Just (MemArray pt _ _ (ArrayIn mem _)) ->+      return $ M.singleton mem (primByteSize pt)+    _ ->+      return mempty

@@ -0,0 +1,161 @@+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE ScopedTypeVariables #-}++-- | Provides last-use analysis for Futhark programs.+module Futhark.Analysis.LastUse (LastUseMap, analyseProg) where++import Data.Bifunctor (first)+import Data.Foldable+import Data.Function ((&))+import Data.Map (Map)+import qualified Data.Map as M+import Data.Tuple+import Futhark.Analysis.Alias (aliasAnalysis)+import Futhark.IR.Aliases+import Futhark.IR.GPUMem++-- | `LastUseMap` tells which names were last used in a given statement.+-- Statements are uniquely identified by the `VName` of the first value+-- parameter in the statement pattern. `Names` is the set of names last used.+type LastUseMap = Map VName Names++-- | `LastUse` is a mapping from a `VName` to the statement identifying it's+-- last use. `LastUseMap` is the inverse of `LastUse`.+type LastUse = Map VName VName++-- | `Used` is the set of `VName` that were used somewhere in a statement, body+-- or otherwise.+type Used = Names++-- | Analyses a program to return a last-use map, mapping each simple statement+-- in the program to the values that were last used within that statement, and+-- the set of all `VName` that were used inside.+analyseProg :: Prog GPUMem -> (LastUseMap, Used)+analyseProg prog =+  let consts =+        progConsts prog+          & concatMap (toList . fmap patElemName . patternValueElements . stmPattern)+          & namesFromList+      funs = progFuns $ aliasAnalysis prog+      (lus, used) = foldMap (analyseFun mempty consts) funs+   in (flipMap lus, used)++analyseFun :: LastUse -> Used -> FunDef (Aliases GPUMem) -> (LastUse, Used)+analyseFun lumap used fun =+  let (lumap', used') = analyseBody lumap used $ funDefBody fun+   in (lumap', used' <> freeIn (funDefParams fun))++analyseStms :: LastUse -> Used -> Stms (Aliases GPUMem) -> (LastUse, Used)+analyseStms lumap used stms = foldr analyseStm (lumap, used) $ stmsToList stms++analyseStm :: Stm (Aliases GPUMem) -> (LastUse, Used) -> (LastUse, Used)+analyseStm (Let pat _ e) (lumap0, used0) =+  let (lumap', used') = patternValueElements pat & foldl helper (lumap0, used0)+   in analyseExp (lumap', used') e+  where+    helper (lumap_acc, used_acc) (PatElem name (aliases, _)) =+      -- Any aliases of `name` should have the same last-use as `name`+      ( case M.lookup name lumap_acc of+          Just name' ->+            insertNames name' (unAliases aliases) lumap_acc+          Nothing -> lumap_acc,+        used_acc <> unAliases aliases+      )++    pat_name = patElemName $ head $ patternValueElements pat+    analyseExp :: (LastUse, Used) -> Exp (Aliases GPUMem) -> (LastUse, Used)+    analyseExp (lumap, used) (BasicOp _) =+      let nms = freeIn e `namesSubtract` used+       in (insertNames pat_name nms lumap, used <> nms)+    analyseExp (lumap, used) (Apply _ args _ _) =+      let nms = freeIn $ map fst args+       in (insertNames pat_name nms lumap, used <> nms)+    analyseExp (lumap, used) (If cse then_body else_body dec) =+      let (lumap_then, used_then) = analyseBody lumap used then_body+          (lumap_else, used_else) = analyseBody lumap used else_body+          used' = used_then <> used_else+          nms = ((freeIn cse <> freeIn dec) `namesSubtract` used')+       in (insertNames pat_name nms (lumap_then <> lumap_else), used' <> nms)+    analyseExp (lumap, used) (DoLoop ctx vals form body) =+      let (lumap', used') = analyseBody lumap used body+          nms = (freeIn ctx <> freeIn vals <> freeIn form) `namesSubtract` used'+       in (insertNames pat_name nms lumap', used' <> nms)+    analyseExp (lumap, used) (Op (Alloc se sp)) =+      let nms = (freeIn se <> freeIn sp) `namesSubtract` used+       in (insertNames pat_name nms lumap, used <> nms)+    analyseExp (lumap, used) (Op (Inner (SizeOp sop))) =+      let nms = freeIn sop `namesSubtract` used+       in (insertNames pat_name nms lumap, used <> nms)+    analyseExp (lumap, used) (Op (Inner (OtherOp ()))) =+      (lumap, used)+    analyseExp (lumap, used) (Op (Inner (SegOp (SegMap lvl _ tps body)))) =+      let (lumap', used') = analyseKernelBody (lumap, used) body+          nms = (freeIn lvl <> freeIn tps) `namesSubtract` used'+       in (insertNames pat_name nms lumap', used' <> nms)+    analyseExp (lumap, used) (Op (Inner (SegOp (SegRed lvl _ binops tps body)))) =+      segOpHelper lumap used lvl binops tps body+    analyseExp (lumap, used) (Op (Inner (SegOp (SegScan lvl _ binops tps body)))) =+      segOpHelper lumap used lvl binops tps body+    analyseExp (lumap, used) (Op (Inner (SegOp (SegHist lvl _ binops tps body)))) =+      let (lumap', used') = foldr analyseHistOp (lumap, used) binops+          (lumap'', used'') = analyseKernelBody (lumap', used') body+          nms = (freeIn lvl <> freeIn tps) `namesSubtract` used''+       in (insertNames pat_name nms lumap'', used'' <> nms)+    analyseExp (lumap, used) (WithAcc _ l) =+      analyseLambda (lumap, used) l+    segOpHelper lumap used lvl binops tps body =+      let (lumap', used') = foldr analyseSegBinOp (lumap, used) binops+          (lumap'', used'') = analyseKernelBody (lumap', used') body+          nms = (freeIn lvl <> freeIn tps) `namesSubtract` used''+       in (insertNames pat_name nms lumap'', used'' <> nms)++analyseBody :: LastUse -> Used -> Body (Aliases GPUMem) -> (LastUse, Used)+analyseBody lumap used (Body _ stms result) =+  let used' = used <> freeIn result+   in analyseStms lumap used' stms++analyseKernelBody ::+  (LastUse, Used) ->+  KernelBody (Aliases GPUMem) ->+  (LastUse, Used)+analyseKernelBody (lumap, used) (KernelBody _ stms result) =+  let used' = used <> freeIn result+   in analyseStms lumap used' stms++analyseSegBinOp ::+  SegBinOp (Aliases GPUMem) ->+  (LastUse, Used) ->+  (LastUse, Used)+analyseSegBinOp (SegBinOp _ lambda neutral shp) (lumap, used) =+  let (lumap', used') = analyseLambda (lumap, used) lambda+      nms = (freeIn neutral <> freeIn shp) `namesSubtract` used'+   in (lumap', used' <> nms)++analyseHistOp ::+  HistOp (Aliases GPUMem) ->+  (LastUse, Used) ->+  (LastUse, Used)+analyseHistOp (HistOp width race dest neutral shp lambda) (lumap, used) =+  let (lumap', used') = analyseLambda (lumap, used) lambda+      nms =+        ( freeIn width <> freeIn race <> freeIn dest <> freeIn neutral+            <> freeIn shp+        )+          `namesSubtract` used'+   in (lumap', used' <> nms)++analyseLambda :: (LastUse, Used) -> Lambda (Aliases GPUMem) -> (LastUse, Used)+analyseLambda (lumap, used) (Lambda params body ret) =+  let (lumap', used') = analyseBody lumap used body+      used'' = used' <> freeIn params <> freeIn ret+   in (lumap', used'')++flipMap :: Map VName VName -> Map VName Names+flipMap m =+  M.toList m+    & fmap (swap . first oneName)+    & foldr (uncurry $ M.insertWith (<>)) mempty++insertNames :: VName -> Names -> LastUse -> LastUse+insertNames name names lumap =+  foldr (flip (M.insertWith $ \_ x -> x) name) lumap $ namesToList names

@@ -80,7 +80,7 @@     addWhat' (ctx, k) = (what : ctx, k)  -- | Compute the metrics for a program.-progMetrics :: OpMetrics (Op lore) => Prog lore -> AstMetrics+progMetrics :: OpMetrics (Op rep) => Prog rep -> AstMetrics progMetrics prog =   actualMetrics $     execWriter $@@ -88,17 +88,17 @@         mapM_ funDefMetrics $ progFuns prog         mapM_ stmMetrics $ progConsts prog -funDefMetrics :: OpMetrics (Op lore) => FunDef lore -> MetricsM ()+funDefMetrics :: OpMetrics (Op rep) => FunDef rep -> MetricsM () funDefMetrics = bodyMetrics . funDefBody -bodyMetrics :: OpMetrics (Op lore) => Body lore -> MetricsM ()+bodyMetrics :: OpMetrics (Op rep) => Body rep -> MetricsM () bodyMetrics = mapM_ stmMetrics . bodyStms  -- | Compute metrics for this statement.-stmMetrics :: OpMetrics (Op lore) => Stm lore -> MetricsM ()+stmMetrics :: OpMetrics (Op rep) => Stm rep -> MetricsM () stmMetrics = expMetrics . stmExp -expMetrics :: OpMetrics (Op lore) => Exp lore -> MetricsM ()+expMetrics :: OpMetrics (Op rep) => Exp rep -> MetricsM () expMetrics (BasicOp op) =   seen "BasicOp" >> primOpMetrics op expMetrics (DoLoop _ _ ForLoop {} body) =@@ -139,5 +139,5 @@ primOpMetrics UpdateAcc {} = seen "UpdateAcc"  -- | Compute metrics for this lambda.-lambdaMetrics :: OpMetrics (Op lore) => Lambda lore -> MetricsM ()+lambdaMetrics :: OpMetrics (Op rep) => Lambda rep -> MetricsM () lambdaMetrics = bodyMetrics . lambdaBody

@@ -60,9 +60,9 @@ -- This includes constants and variable names, which are passed as -- t'SubExp's. primExpFromExp ::-  (Fail.MonadFail m, Decorations lore) =>+  (Fail.MonadFail m, RepTypes rep) =>   (VName -> m (PrimExp v)) ->-  Exp lore ->+  Exp rep ->   m (PrimExp v) primExpFromExp f (BasicOp (BinOp op x y)) =   BinOpExp op <$> primExpFromSubExpM f x <*> primExpFromSubExpM f y

@@ -11,9 +11,9 @@ -- refers to a name that is a 'Constant', the node turns into a -- 'ValueExp'. simplifyPrimExp ::-  SimplifiableLore lore =>+  SimplifiableRep rep =>   PrimExp VName ->-  SimpleM lore (PrimExp VName)+  SimpleM rep (PrimExp VName) simplifyPrimExp = simplifyAnyPrimExp onLeaf   where     onLeaf v pt = do@@ -24,9 +24,9 @@  -- | Like 'simplifyPrimExp', but where leaves may be 'Ext's. simplifyExtPrimExp ::-  SimplifiableLore lore =>+  SimplifiableRep rep =>   PrimExp (Ext VName) ->-  SimpleM lore (PrimExp (Ext VName))+  SimpleM rep (PrimExp (Ext VName)) simplifyExtPrimExp = simplifyAnyPrimExp onLeaf   where     onLeaf (Free v) pt = do@@ -37,10 +37,10 @@     onLeaf (Ext i) pt = return $ LeafExp (Ext i) pt  simplifyAnyPrimExp ::-  SimplifiableLore lore =>-  (a -> PrimType -> SimpleM lore (PrimExp a)) ->+  SimplifiableRep rep =>+  (a -> PrimType -> SimpleM rep (PrimExp a)) ->   PrimExp a ->-  SimpleM lore (PrimExp a)+  SimpleM rep (PrimExp a) simplifyAnyPrimExp f (LeafExp v pt) = f v pt simplifyAnyPrimExp _ (ValueExp pv) =   return $ ValueExp pv

@@ -1,6 +1,6 @@ {-# LANGUAGE ConstraintKinds #-} --- | Facilities for changing the lore of some fragment, with no+-- | Facilities for changing the rep of some fragment, with no -- context.  We call this "rephrasing", for no deep reason. module Futhark.Analysis.Rephrase   ( rephraseProg,@@ -20,14 +20,14 @@ -- | A collection of functions that together allow us to rephrase some -- IR fragment, in some monad @m@.  If we let @m@ be the 'Maybe' -- monad, we can conveniently do rephrasing that might fail.  This is--- useful if you want to see if some IR in e.g. the @Kernels@ lore+-- useful if you want to see if some IR in e.g. the @Kernels@ rep -- actually uses any @Kernels@-specific operations. data Rephraser m from to = Rephraser-  { rephraseExpLore :: ExpDec from -> m (ExpDec to),-    rephraseLetBoundLore :: LetDec from -> m (LetDec to),-    rephraseFParamLore :: FParamInfo from -> m (FParamInfo to),-    rephraseLParamLore :: LParamInfo from -> m (LParamInfo to),-    rephraseBodyLore :: BodyDec from -> m (BodyDec to),+  { rephraseExpDec :: ExpDec from -> m (ExpDec to),+    rephraseLetBoundDec :: LetDec from -> m (LetDec to),+    rephraseFParamDec :: FParamInfo from -> m (FParamInfo to),+    rephraseLParamDec :: LParamInfo from -> m (LParamInfo to),+    rephraseBodyDec :: BodyDec from -> m (BodyDec to),     rephraseRetType :: RetType from -> m (RetType to),     rephraseBranchType :: BranchType from -> m (BranchType to),     rephraseOp :: Op from -> m (Op to)@@ -44,7 +44,7 @@ rephraseFunDef :: Monad m => Rephraser m from to -> FunDef from -> m (FunDef to) rephraseFunDef rephraser fundec = do   body' <- rephraseBody rephraser $ funDefBody fundec-  params' <- mapM (rephraseParam $ rephraseFParamLore rephraser) $ funDefParams fundec+  params' <- mapM (rephraseParam $ rephraseFParamDec rephraser) $ funDefParams fundec   rettype' <- mapM (rephraseRetType rephraser) $ funDefRetType fundec   return fundec {funDefBody = body', funDefParams = params', funDefRetType = rettype'} @@ -56,8 +56,8 @@ rephraseStm :: Monad m => Rephraser m from to -> Stm from -> m (Stm to) rephraseStm rephraser (Let pat (StmAux cs attrs dec) e) =   Let-    <$> rephrasePattern (rephraseLetBoundLore rephraser) pat-    <*> (StmAux cs attrs <$> rephraseExpLore rephraser dec)+    <$> rephrasePattern (rephraseLetBoundDec rephraser) pat+    <*> (StmAux cs attrs <$> rephraseExpDec rephraser dec)     <*> rephraseExp rephraser e  -- | Rephrase a pattern.@@ -80,9 +80,9 @@  -- | Rephrase a body. rephraseBody :: Monad m => Rephraser m from to -> Body from -> m (Body to)-rephraseBody rephraser (Body lore bnds res) =+rephraseBody rephraser (Body rep bnds res) =   Body-    <$> rephraseBodyLore rephraser lore+    <$> rephraseBodyDec rephraser rep     <*> (stmsFromList <$> mapM (rephraseStm rephraser) (stmsToList bnds))     <*> pure res @@ -90,7 +90,7 @@ rephraseLambda :: Monad m => Rephraser m from to -> Lambda from -> m (Lambda to) rephraseLambda rephraser lam = do   body' <- rephraseBody rephraser $ lambdaBody lam-  params' <- mapM (rephraseParam $ rephraseLParamLore rephraser) $ lambdaParams lam+  params' <- mapM (rephraseParam $ rephraseLParamDec rephraser) $ lambdaParams lam   return lam {lambdaBody = body', lambdaParams = params'}  mapper :: Monad m => Rephraser m from to -> Mapper from to m@@ -99,7 +99,7 @@     { mapOnBody = const $ rephraseBody rephraser,       mapOnRetType = rephraseRetType rephraser,       mapOnBranchType = rephraseBranchType rephraser,-      mapOnFParam = rephraseParam (rephraseFParamLore rephraser),-      mapOnLParam = rephraseParam (rephraseLParamLore rephraser),+      mapOnFParam = rephraseParam (rephraseFParamDec rephraser),+      mapOnLParam = rephraseParam (rephraseLParamDec rephraser),       mapOnOp = rephraseOp rephraser     }

@@ -61,9 +61,9 @@ import qualified Futhark.IR.Prop.Aliases as Aliases import Prelude hiding (elem, lookup) -data SymbolTable lore = SymbolTable+data SymbolTable rep = SymbolTable   { loopDepth :: Int,-    bindings :: M.Map VName (Entry lore),+    bindings :: M.Map VName (Entry rep),     -- | Which names are available just before the most enclosing     -- loop?     availableAtClosestLoop :: Names,@@ -73,7 +73,7 @@     simplifyMemory :: Bool   } -instance Semigroup (SymbolTable lore) where+instance Semigroup (SymbolTable rep) where   table1 <> table2 =     SymbolTable       { loopDepth = max (loopDepth table1) (loopDepth table2),@@ -84,21 +84,21 @@         simplifyMemory = simplifyMemory table1 || simplifyMemory table2       } -instance Monoid (SymbolTable lore) where+instance Monoid (SymbolTable rep) where   mempty = empty -empty :: SymbolTable lore+empty :: SymbolTable rep empty = SymbolTable 0 M.empty mempty False -fromScope :: ASTLore lore => Scope lore -> SymbolTable lore+fromScope :: ASTRep rep => Scope rep -> SymbolTable rep fromScope = M.foldlWithKey' insertFreeVar' empty   where     insertFreeVar' m k dec = insertFreeVar k dec m -toScope :: SymbolTable lore -> Scope lore+toScope :: SymbolTable rep -> Scope rep toScope = M.map entryInfo . bindings -deepen :: SymbolTable lore -> SymbolTable lore+deepen :: SymbolTable rep -> SymbolTable rep deepen vtable =   vtable     { loopDepth = loopDepth vtable + 1,@@ -125,59 +125,59 @@ -- | Indexing a delayed array if possible. type IndexArray = [TPrimExp Int64 VName] -> Maybe Indexed -data Entry lore = Entry+data Entry rep = Entry   { -- | True if consumed.     entryConsumed :: Bool,     entryDepth :: Int,     -- | True if this name has been used as an array size,     -- implying that it is non-negative.     entryIsSize :: Bool,-    entryType :: EntryType lore+    entryType :: EntryType rep   } -data EntryType lore-  = LoopVar (LoopVarEntry lore)-  | LetBound (LetBoundEntry lore)-  | FParam (FParamEntry lore)-  | LParam (LParamEntry lore)-  | FreeVar (FreeVarEntry lore)+data EntryType rep+  = LoopVar (LoopVarEntry rep)+  | LetBound (LetBoundEntry rep)+  | FParam (FParamEntry rep)+  | LParam (LParamEntry rep)+  | FreeVar (FreeVarEntry rep) -data LoopVarEntry lore = LoopVarEntry+data LoopVarEntry rep = LoopVarEntry   { loopVarType :: IntType,     loopVarBound :: SubExp   } -data LetBoundEntry lore = LetBoundEntry-  { letBoundDec :: LetDec lore,+data LetBoundEntry rep = LetBoundEntry+  { letBoundDec :: LetDec rep,     letBoundAliases :: Names,-    letBoundStm :: Stm lore,+    letBoundStm :: Stm rep,     -- | Index a delayed array, if possible.     letBoundIndex :: Int -> IndexArray   } -data FParamEntry lore = FParamEntry-  { fparamDec :: FParamInfo lore,+data FParamEntry rep = FParamEntry+  { fparamDec :: FParamInfo rep,     fparamAliases :: Names,     -- | If a loop parameter, the initial value and the eventual     -- result.  The result need not be in scope in the symbol table.     fparamMerge :: Maybe (SubExp, SubExp)   } -data LParamEntry lore = LParamEntry-  { lparamDec :: LParamInfo lore,+data LParamEntry rep = LParamEntry+  { lparamDec :: LParamInfo rep,     lparamIndex :: IndexArray   } -data FreeVarEntry lore = FreeVarEntry-  { freeVarDec :: NameInfo lore,+data FreeVarEntry rep = FreeVarEntry+  { freeVarDec :: NameInfo rep,     -- | Index a delayed array, if possible.     freeVarIndex :: VName -> IndexArray   } -instance ASTLore lore => Typed (Entry lore) where+instance ASTRep rep => Typed (Entry rep) where   typeOf = typeOf . entryInfo -entryInfo :: Entry lore -> NameInfo lore+entryInfo :: Entry rep -> NameInfo rep entryInfo e = case entryType e of   LetBound entry -> LetName $ letBoundDec entry   LoopVar entry -> IndexName $ loopVarType entry@@ -185,54 +185,54 @@   LParam entry -> LParamName $ lparamDec entry   FreeVar entry -> freeVarDec entry -isLetBound :: Entry lore -> Maybe (LetBoundEntry lore)+isLetBound :: Entry rep -> Maybe (LetBoundEntry rep) isLetBound e = case entryType e of   LetBound entry -> Just entry   _ -> Nothing -entryStm :: Entry lore -> Maybe (Stm lore)+entryStm :: Entry rep -> Maybe (Stm rep) entryStm = fmap letBoundStm . isLetBound -entryFParam :: Entry lore -> Maybe (FParamInfo lore)+entryFParam :: Entry rep -> Maybe (FParamInfo rep) entryFParam e = case entryType e of   FParam e' -> Just $ fparamDec e'   _ -> Nothing -entryLetBoundDec :: Entry lore -> Maybe (LetDec lore)+entryLetBoundDec :: Entry rep -> Maybe (LetDec rep) entryLetBoundDec = fmap letBoundDec . isLetBound -elem :: VName -> SymbolTable lore -> Bool+elem :: VName -> SymbolTable rep -> Bool elem name = isJust . lookup name -lookup :: VName -> SymbolTable lore -> Maybe (Entry lore)+lookup :: VName -> SymbolTable rep -> Maybe (Entry rep) lookup name = M.lookup name . bindings -lookupStm :: VName -> SymbolTable lore -> Maybe (Stm lore)+lookupStm :: VName -> SymbolTable rep -> Maybe (Stm rep) lookupStm name vtable = entryStm =<< lookup name vtable -lookupExp :: VName -> SymbolTable lore -> Maybe (Exp lore, Certificates)+lookupExp :: VName -> SymbolTable rep -> Maybe (Exp rep, Certificates) lookupExp name vtable = (stmExp &&& stmCerts) <$> lookupStm name vtable -lookupBasicOp :: VName -> SymbolTable lore -> Maybe (BasicOp, Certificates)+lookupBasicOp :: VName -> SymbolTable rep -> Maybe (BasicOp, Certificates) lookupBasicOp name vtable = case lookupExp name vtable of   Just (BasicOp e, cs) -> Just (e, cs)   _ -> Nothing -lookupType :: ASTLore lore => VName -> SymbolTable lore -> Maybe Type+lookupType :: ASTRep rep => VName -> SymbolTable rep -> Maybe Type lookupType name vtable = typeOf <$> lookup name vtable -lookupSubExpType :: ASTLore lore => SubExp -> SymbolTable lore -> Maybe Type+lookupSubExpType :: ASTRep rep => SubExp -> SymbolTable rep -> Maybe Type lookupSubExpType (Var v) = lookupType v lookupSubExpType (Constant v) = const $ Just $ Prim $ primValueType v -lookupSubExp :: VName -> SymbolTable lore -> Maybe (SubExp, Certificates)+lookupSubExp :: VName -> SymbolTable rep -> Maybe (SubExp, Certificates) lookupSubExp name vtable = do   (e, cs) <- lookupExp name vtable   case e of     BasicOp (SubExp se) -> Just (se, cs)     _ -> Nothing -lookupAliases :: VName -> SymbolTable lore -> Names+lookupAliases :: VName -> SymbolTable rep -> Names lookupAliases name vtable =   case entryType <$> M.lookup name (bindings vtable) of     Just (LetBound e) -> letBoundAliases e@@ -241,25 +241,25 @@  -- | If the given variable name is the name of a 'ForLoop' parameter, -- then return the bound of that loop.-lookupLoopVar :: VName -> SymbolTable lore -> Maybe SubExp+lookupLoopVar :: VName -> SymbolTable rep -> Maybe SubExp lookupLoopVar name vtable = do   LoopVar e <- entryType <$> M.lookup name (bindings vtable)   return $ loopVarBound e -lookupLoopParam :: VName -> SymbolTable lore -> Maybe (SubExp, SubExp)+lookupLoopParam :: VName -> SymbolTable rep -> Maybe (SubExp, SubExp) lookupLoopParam name vtable = do   FParam e <- entryType <$> M.lookup name (bindings vtable)   fparamMerge e  -- | In symbol table and not consumed.-available :: VName -> SymbolTable lore -> Bool+available :: VName -> SymbolTable rep -> Bool available name = maybe False (not . entryConsumed) . M.lookup name . bindings  index ::-  ASTLore lore =>+  ASTRep rep =>   VName ->   [SubExp] ->-  SymbolTable lore ->+  SymbolTable rep ->   Maybe Indexed index name is table = do   is' <- mapM asPrimExp is@@ -272,7 +272,7 @@ index' ::   VName ->   [TPrimExp Int64 VName] ->-  SymbolTable lore ->+  SymbolTable rep ->   Maybe Indexed index' name is vtable = do   entry <- lookup name vtable@@ -290,8 +290,8 @@  class IndexOp op where   indexOp ::-    (ASTLore lore, IndexOp (Op lore)) =>-    SymbolTable lore ->+    (ASTRep rep, IndexOp (Op rep)) =>+    SymbolTable rep ->     Int ->     op ->     [TPrimExp Int64 VName] ->@@ -301,9 +301,9 @@ instance IndexOp ()  indexExp ::-  (IndexOp (Op lore), ASTLore lore) =>-  SymbolTable lore ->-  Exp lore ->+  (IndexOp (Op rep), ASTRep rep) =>+  SymbolTable rep ->+  Exp rep ->   Int ->   IndexArray indexExp vtable (Op op) k is =@@ -345,12 +345,12 @@ indexExp _ _ _ _ = Nothing  defBndEntry ::-  (ASTLore lore, IndexOp (Op lore)) =>-  SymbolTable lore ->-  PatElem lore ->+  (ASTRep rep, IndexOp (Op rep)) =>+  SymbolTable rep ->+  PatElem rep ->   Names ->-  Stm lore ->-  LetBoundEntry lore+  Stm rep ->+  LetBoundEntry rep defBndEntry vtable patElem als bnd =   LetBoundEntry     { letBoundDec = patElemDec patElem,@@ -362,10 +362,10 @@     }  bindingEntries ::-  (ASTLore lore, Aliases.Aliased lore, IndexOp (Op lore)) =>-  Stm lore ->-  SymbolTable lore ->-  [LetBoundEntry lore]+  (ASTRep rep, Aliases.Aliased rep, IndexOp (Op rep)) =>+  Stm rep ->+  SymbolTable rep ->+  [LetBoundEntry rep] bindingEntries bnd@(Let pat _ _) vtable = do   pat_elem <- patternElements pat   return $ defBndEntry vtable pat_elem (Aliases.aliasesOf pat_elem) bnd@@ -374,11 +374,11 @@ adjustSeveral f = flip $ foldl' $ flip $ M.adjust f  insertEntry ::-  ASTLore lore =>+  ASTRep rep =>   VName ->-  EntryType lore ->-  SymbolTable lore ->-  SymbolTable lore+  EntryType rep ->+  SymbolTable rep ->+  SymbolTable rep insertEntry name entry vtable =   let entry' =         Entry@@ -396,20 +396,20 @@         }  insertEntries ::-  ASTLore lore =>-  [(VName, EntryType lore)] ->-  SymbolTable lore ->-  SymbolTable lore+  ASTRep rep =>+  [(VName, EntryType rep)] ->+  SymbolTable rep ->+  SymbolTable rep insertEntries entries vtable =   foldl' add vtable entries   where     add vtable' (name, entry) = insertEntry name entry vtable'  insertStm ::-  (ASTLore lore, IndexOp (Op lore), Aliases.Aliased lore) =>-  Stm lore ->-  SymbolTable lore ->-  SymbolTable lore+  (ASTRep rep, IndexOp (Op rep), Aliases.Aliased rep) =>+  Stm rep ->+  SymbolTable rep ->+  SymbolTable rep insertStm stm vtable =   flip (foldl' $ flip consume) (namesToList stm_consumed) $     flip (foldl' addRevAliases) (patternElements $ stmPattern stm) $@@ -435,23 +435,23 @@         update' e = e  insertStms ::-  (ASTLore lore, IndexOp (Op lore), Aliases.Aliased lore) =>-  Stms lore ->-  SymbolTable lore ->-  SymbolTable lore+  (ASTRep rep, IndexOp (Op rep), Aliases.Aliased rep) =>+  Stms rep ->+  SymbolTable rep ->+  SymbolTable rep insertStms stms vtable = foldl' (flip insertStm) vtable $ stmsToList stms -expandAliases :: Names -> SymbolTable lore -> Names+expandAliases :: Names -> SymbolTable rep -> Names expandAliases names vtable = names <> aliasesOfAliases   where     aliasesOfAliases =       mconcat . map (`lookupAliases` vtable) . namesToList $ names  insertFParam ::-  ASTLore lore =>-  AST.FParam lore ->-  SymbolTable lore ->-  SymbolTable lore+  ASTRep rep =>+  AST.FParam rep ->+  SymbolTable rep ->+  SymbolTable rep insertFParam fparam = insertEntry name entry   where     name = AST.paramName fparam@@ -464,13 +464,13 @@           }  insertFParams ::-  ASTLore lore =>-  [AST.FParam lore] ->-  SymbolTable lore ->-  SymbolTable lore+  ASTRep rep =>+  [AST.FParam rep] ->+  SymbolTable rep ->+  SymbolTable rep insertFParams fparams symtable = foldl' (flip insertFParam) symtable fparams -insertLParam :: ASTLore lore => LParam lore -> SymbolTable lore -> SymbolTable lore+insertLParam :: ASTRep rep => LParam rep -> SymbolTable rep -> SymbolTable rep insertLParam param = insertEntry name bind   where     bind =@@ -489,10 +489,10 @@ -- used to help some loop optimisations detect invariant loop -- parameters. insertLoopMerge ::-  ASTLore lore =>-  [(AST.FParam lore, SubExp, SubExp)] ->-  SymbolTable lore ->-  SymbolTable lore+  ASTRep rep =>+  [(AST.FParam rep, SubExp, SubExp)] ->+  SymbolTable rep ->+  SymbolTable rep insertLoopMerge = flip $ foldl' $ flip bind   where     bind (p, initial, res) =@@ -504,7 +504,7 @@               fparamMerge = Just (initial, res)             } -insertLoopVar :: ASTLore lore => VName -> IntType -> SubExp -> SymbolTable lore -> SymbolTable lore+insertLoopVar :: ASTRep rep => VName -> IntType -> SubExp -> SymbolTable rep -> SymbolTable rep insertLoopVar name it bound = insertEntry name bind   where     bind =@@ -514,7 +514,7 @@             loopVarBound = bound           } -insertFreeVar :: ASTLore lore => VName -> NameInfo lore -> SymbolTable lore -> SymbolTable lore+insertFreeVar :: ASTRep rep => VName -> NameInfo rep -> SymbolTable rep -> SymbolTable rep insertFreeVar name dec = insertEntry name entry   where     entry =@@ -524,7 +524,7 @@             freeVarIndex = \_ _ -> Nothing           } -consume :: VName -> SymbolTable lore -> SymbolTable lore+consume :: VName -> SymbolTable rep -> SymbolTable rep consume consumee vtable =   foldl' consume' vtable $     namesToList $@@ -535,7 +535,7 @@     consume'' e = e {entryConsumed = True}  -- | Hide definitions of those entries that satisfy some predicate.-hideIf :: (Entry lore -> Bool) -> SymbolTable lore -> SymbolTable lore+hideIf :: (Entry rep -> Bool) -> SymbolTable rep -> SymbolTable rep hideIf hide vtable = vtable {bindings = M.map maybeHide $ bindings vtable}   where     maybeHide entry@@ -552,7 +552,7 @@  -- | Hide these definitions, if they are protected by certificates in -- the set of names.-hideCertified :: Names -> SymbolTable lore -> SymbolTable lore+hideCertified :: Names -> SymbolTable rep -> SymbolTable rep hideCertified to_hide = hideIf $ maybe False hide . entryStm   where     hide = any (`nameIn` to_hide) . unCertificates . stmCerts

@@ -141,16 +141,16 @@ withoutU :: Usages -> Usages -> Usages withoutU (Usages x) (Usages y) = Usages $ x .&. complement y -usageInBody :: Aliased lore => Body lore -> UsageTable+usageInBody :: Aliased rep => Body rep -> UsageTable usageInBody = foldMap consumedUsage . namesToList . consumedInBody  -- | Produce a usage table reflecting the use of the free variables in -- a single statement.-usageInStm :: (ASTLore lore, Aliased lore) => Stm lore -> UsageTable-usageInStm (Let pat lore e) =+usageInStm :: (ASTRep rep, Aliased rep) => Stm rep -> UsageTable+usageInStm (Let pat rep e) =   mconcat     [ usageInPat,-      usageInExpLore,+      usageInExpDec,       usageInExp e,       usages (freeIn e)     ]@@ -161,10 +161,10 @@             `namesSubtract` namesFromList (patternNames pat)         )         <> sizeUsages (foldMap (freeIn . patElemType) (patternElements pat))-    usageInExpLore =-      usages $ freeIn lore+    usageInExpDec =+      usages $ freeIn rep -usageInExp :: Aliased lore => Exp lore -> UsageTable+usageInExp :: Aliased rep => Exp rep -> UsageTable usageInExp (Apply _ args _ _) =   mconcat     [ mconcat $

@@ -158,11 +158,13 @@    cmdMaybe . liftIO $ cmdClear server -  valuesAsVars server (zip ins input_types) futhark dir input_spec-   let freeOuts = cmdMaybe (cmdFree server outs)       freeIns = cmdMaybe (cmdFree server ins)+      loadInput = valuesAsVars server (zip ins $ map inputType input_types) futhark dir input_spec+      reloadInput = freeIns >> loadInput +  loadInput+   let runtime l         | Just l' <- T.stripPrefix "runtime: " l,           [(x, "")] <- reads $ T.unpack l' =@@ -172,6 +174,7 @@        doRun = do         call_lines <- cmdEither (cmdCall server entry outs ins)+        when (any inputConsumed input_types) reloadInput         case mapMaybe runtime call_lines of           [call_runtime] -> do             liftIO $ fromMaybe (const $ pure ()) (runResultAction opts) call_runtime@@ -197,7 +200,7 @@    report <- cmdEither $ cmdReport server -  vs <- readResults server outs program <* freeOuts+  vs <- readResults server outs <* freeOuts    maybe_expected <-     liftIO $ maybe (return Nothing) (fmap Just . getExpectedValues) expected_spec

@@ -42,44 +42,44 @@ import Futhark.IR  -- | A 'BinderT' (and by extension, a 'Binder') is only an instance of--- 'MonadBinder' for lores that implement this type class, which--- contains methods for constructing statements.-class ASTLore lore => BinderOps lore where+-- 'MonadBinder' for representations that implement this type class,+-- which contains methods for constructing statements.+class ASTRep rep => BinderOps rep where   mkExpDecB ::-    (MonadBinder m, Lore m ~ lore) =>-    Pattern lore ->-    Exp lore ->-    m (ExpDec lore)+    (MonadBinder m, Rep m ~ rep) =>+    Pattern rep ->+    Exp rep ->+    m (ExpDec rep)   mkBodyB ::-    (MonadBinder m, Lore m ~ lore) =>-    Stms lore ->+    (MonadBinder m, Rep m ~ rep) =>+    Stms rep ->     Result ->-    m (Body lore)+    m (Body rep)   mkLetNamesB ::-    (MonadBinder m, Lore m ~ lore) =>+    (MonadBinder m, Rep m ~ rep) =>     [VName] ->-    Exp lore ->-    m (Stm lore)+    Exp rep ->+    m (Stm rep)    default mkExpDecB ::-    (MonadBinder m, Bindable lore) =>-    Pattern lore ->-    Exp lore ->-    m (ExpDec lore)+    (MonadBinder m, Bindable rep) =>+    Pattern rep ->+    Exp rep ->+    m (ExpDec rep)   mkExpDecB pat e = return $ mkExpDec pat e    default mkBodyB ::-    (MonadBinder m, Bindable lore) =>-    Stms lore ->+    (MonadBinder m, Bindable rep) =>+    Stms rep ->     Result ->-    m (Body lore)+    m (Body rep)   mkBodyB stms res = return $ mkBody stms res    default mkLetNamesB ::-    (MonadBinder m, Lore m ~ lore, Bindable lore) =>+    (MonadBinder m, Rep m ~ rep, Bindable rep) =>     [VName] ->-    Exp lore ->-    m (Stm lore)+    Exp rep ->+    m (Stm rep)   mkLetNamesB = mkLetNames  -- | A monad transformer that tracks statements and provides a@@ -88,22 +88,22 @@ -- constructing statements (possibly as part of a larger monad stack). -- If you find yourself needing to implement 'MonadBinder' from -- scratch, then it is likely that you are making a mistake.-newtype BinderT lore m a = BinderT (StateT (Stms lore, Scope lore) m a)+newtype BinderT rep m a = BinderT (StateT (Stms rep, Scope rep) m a)   deriving (Functor, Monad, Applicative) -instance MonadTrans (BinderT lore) where+instance MonadTrans (BinderT rep) where   lift = BinderT . lift  -- | The most commonly used binder monad.-type Binder lore = BinderT lore (State VNameSource)+type Binder rep = BinderT rep (State VNameSource) -instance MonadFreshNames m => MonadFreshNames (BinderT lore m) where+instance MonadFreshNames m => MonadFreshNames (BinderT rep m) where   getNameSource = lift getNameSource   putNameSource = lift . putNameSource  instance-  (ASTLore lore, Monad m) =>-  HasScope lore (BinderT lore m)+  (ASTRep rep, Monad m) =>+  HasScope rep (BinderT rep m)   where   lookupType name = do     t <- BinderT $ gets $ M.lookup name . snd@@ -113,8 +113,8 @@   askScope = BinderT $ gets snd  instance-  (ASTLore lore, Monad m) =>-  LocalScope lore (BinderT lore m)+  (ASTRep rep, Monad m) =>+  LocalScope rep (BinderT rep m)   where   localScope types (BinderT m) = BinderT $ do     modify $ second (M.union types)@@ -123,10 +123,10 @@     return x  instance-  (ASTLore lore, MonadFreshNames m, BinderOps lore) =>-  MonadBinder (BinderT lore m)+  (ASTRep rep, MonadFreshNames m, BinderOps rep) =>+  MonadBinder (BinderT rep m)   where-  type Lore (BinderT lore m) = lore+  type Rep (BinderT rep m) = rep   mkExpDecM = mkExpDecB   mkBodyM = mkBodyB   mkLetNamesM = mkLetNamesB@@ -148,9 +148,9 @@ -- the statements added ('addStm') during the action. runBinderT ::   MonadFreshNames m =>-  BinderT lore m a ->-  Scope lore ->-  m (a, Stms lore)+  BinderT rep m a ->+  Scope rep ->+  m (a, Stms rep) runBinderT (BinderT m) scope = do   (x, (stms, _)) <- runStateT m (mempty, scope)   return (x, stms)@@ -158,17 +158,17 @@ -- | Like 'runBinderT', but return only the statements. runBinderT_ ::   MonadFreshNames m =>-  BinderT lore m () ->-  Scope lore ->-  m (Stms lore)+  BinderT rep m () ->+  Scope rep ->+  m (Stms rep) runBinderT_ m = fmap snd . runBinderT m  -- | Like 'runBinderT', but get the initial scope from the current -- monad. runBinderT' ::-  (MonadFreshNames m, HasScope somelore m, SameScope somelore lore) =>-  BinderT lore m a ->-  m (a, Stms lore)+  (MonadFreshNames m, HasScope somerep m, SameScope somerep rep) =>+  BinderT rep m a ->+  m (a, Stms rep) runBinderT' m = do   scope <- askScope   runBinderT m $ castScope scope@@ -176,9 +176,9 @@ -- | Like 'runBinderT_', but get the initial scope from the current -- monad. runBinderT'_ ::-  (MonadFreshNames m, HasScope somelore m, SameScope somelore lore) =>-  BinderT lore m a ->-  m (Stms lore)+  (MonadFreshNames m, HasScope somerep m, SameScope somerep rep) =>+  BinderT rep m a ->+  m (Stms rep) runBinderT'_ = fmap snd . runBinderT'  -- | Run a binder action, returning a value and the statements added@@ -186,11 +186,11 @@ -- provides initial scope and name source. runBinder ::   ( MonadFreshNames m,-    HasScope somelore m,-    SameScope somelore lore+    HasScope somerep m,+    SameScope somerep rep   ) =>-  Binder lore a ->-  m (a, Stms lore)+  Binder rep a ->+  m (a, Stms rep) runBinder m = do   types <- askScope   modifyNameSource $ runState $ runBinderT m $ castScope types@@ -199,23 +199,23 @@ -- added statements. runBinder_ ::   ( MonadFreshNames m,-    HasScope somelore m,-    SameScope somelore lore+    HasScope somerep m,+    SameScope somerep rep   ) =>-  Binder lore a ->-  m (Stms lore)+  Binder rep a ->+  m (Stms rep) runBinder_ = fmap snd . runBinder  -- | Run a binder that produces a t'Body', and prefix that t'Body' by -- the statements produced during execution of the action. runBodyBinder ::-  ( Bindable lore,+  ( Bindable rep,     MonadFreshNames m,-    HasScope somelore m,-    SameScope somelore lore+    HasScope somerep m,+    SameScope somerep rep   ) =>-  Binder lore (Body lore) ->-  m (Body lore)+  Binder rep (Body rep) ->+  m (Body rep) runBodyBinder = fmap (uncurry $ flip insertStms) . runBinder  -- Utility instance defintions for MTL classes.  These require@@ -223,26 +223,26 @@  mapInner ::   Monad m =>-  ( m (a, (Stms lore, Scope lore)) ->-    m (b, (Stms lore, Scope lore))+  ( m (a, (Stms rep, Scope rep)) ->+    m (b, (Stms rep, Scope rep))   ) ->-  BinderT lore m a ->-  BinderT lore m b+  BinderT rep m a ->+  BinderT rep m b mapInner f (BinderT m) = BinderT $ do   s <- get   (x, s') <- lift $ f $ runStateT m s   put s'   return x -instance MonadReader r m => MonadReader r (BinderT lore m) where+instance MonadReader r m => MonadReader r (BinderT rep m) where   ask = BinderT $ lift ask   local f = mapInner $ local f -instance MonadState s m => MonadState s (BinderT lore m) where+instance MonadState s m => MonadState s (BinderT rep m) where   get = BinderT $ lift get   put = BinderT . lift . put -instance MonadWriter w m => MonadWriter w (BinderT lore m) where+instance MonadWriter w m => MonadWriter w (BinderT rep m) where   tell = BinderT . lift . tell   pass = mapInner $ \m -> pass $ do     ((x, f), s) <- m@@ -251,7 +251,7 @@     ((x, s), y) <- listen m     return ((x, y), s) -instance MonadError e m => MonadError e (BinderT lore m) where+instance MonadError e m => MonadError e (BinderT rep m) where   throwError = lift . throwError   catchError (BinderT m) f =     BinderT $ catchError m $ unBinder . f

@@ -26,33 +26,33 @@ import Futhark.IR import Futhark.MonadFreshNames --- | The class of lores that can be constructed solely from an--- expression, within some monad.  Very important: the methods should--- not have any significant side effects!  They may be called more--- often than you think, and the results thrown away.  If used+-- | The class of representations that can be constructed solely from+-- an expression, within some monad.  Very important: the methods+-- should not have any significant side effects!  They may be called+-- more often than you think, and the results thrown away.  If used -- exclusively within a 'MonadBinder' instance, it is acceptable for -- them to create new bindings, however. class-  ( ASTLore lore,-    FParamInfo lore ~ DeclType,-    LParamInfo lore ~ Type,-    RetType lore ~ DeclExtType,-    BranchType lore ~ ExtType,-    SetType (LetDec lore)+  ( ASTRep rep,+    FParamInfo rep ~ DeclType,+    LParamInfo rep ~ Type,+    RetType rep ~ DeclExtType,+    BranchType rep ~ ExtType,+    SetType (LetDec rep)   ) =>-  Bindable lore+  Bindable rep   where-  mkExpPat :: [Ident] -> [Ident] -> Exp lore -> Pattern lore-  mkExpDec :: Pattern lore -> Exp lore -> ExpDec lore-  mkBody :: Stms lore -> Result -> Body lore+  mkExpPat :: [Ident] -> [Ident] -> Exp rep -> Pattern rep+  mkExpDec :: Pattern rep -> Exp rep -> ExpDec rep+  mkBody :: Stms rep -> Result -> Body rep   mkLetNames ::-    (MonadFreshNames m, HasScope lore m) =>+    (MonadFreshNames m, HasScope rep m) =>     [VName] ->-    Exp lore ->-    m (Stm lore)+    Exp rep ->+    m (Stm rep)  -- | A monad that supports the creation of bindings from expressions--- and bodies from bindings, with a specific lore.  This is the main+-- and bodies from bindings, with a specific rep.  This is the main -- typeclass that a monad must implement in order for it to be useful -- for generating or modifying Futhark code.  Most importantly -- maintains a current state of 'Stms' (as well as a 'Scope') that@@ -63,29 +63,29 @@ -- results thrown away.  It is acceptable for them to create new -- bindings, however. class-  ( ASTLore (Lore m),+  ( ASTRep (Rep m),     MonadFreshNames m,     Applicative m,     Monad m,-    LocalScope (Lore m) m+    LocalScope (Rep m) m   ) =>   MonadBinder m   where-  type Lore m :: Data.Kind.Type-  mkExpDecM :: Pattern (Lore m) -> Exp (Lore m) -> m (ExpDec (Lore m))-  mkBodyM :: Stms (Lore m) -> Result -> m (Body (Lore m))-  mkLetNamesM :: [VName] -> Exp (Lore m) -> m (Stm (Lore m))+  type Rep m :: Data.Kind.Type+  mkExpDecM :: Pattern (Rep m) -> Exp (Rep m) -> m (ExpDec (Rep m))+  mkBodyM :: Stms (Rep m) -> Result -> m (Body (Rep m))+  mkLetNamesM :: [VName] -> Exp (Rep m) -> m (Stm (Rep m))    -- | Add a statement to the 'Stms' under construction.-  addStm :: Stm (Lore m) -> m ()+  addStm :: Stm (Rep m) -> m ()   addStm = addStms . oneStm    -- | Add multiple statements to the 'Stms' under construction.-  addStms :: Stms (Lore m) -> m ()+  addStms :: Stms (Rep m) -> m ()    -- | Obtain the statements constructed during a monadic action,   -- instead of adding them to the state.-  collectStms :: m a -> m (a, Stms (Lore m))+  collectStms :: m a -> m (a, Stms (Rep m))    -- | Add the provided certificates to any statements added during   -- execution of the action.@@ -95,7 +95,7 @@ -- | Apply a function to the statements added by this action. censorStms ::   MonadBinder m =>-  (Stms (Lore m) -> Stms (Lore m)) ->+  (Stms (Rep m) -> Stms (Rep m)) ->   m a ->   m a censorStms f m = do@@ -112,7 +112,7 @@  -- | Add the certificates and attributes to any statements added by -- this action.-auxing :: MonadBinder m => StmAux anylore -> m a -> m a+auxing :: MonadBinder m => StmAux anyrep -> m a -> m a auxing (StmAux cs attrs _) = censorStms $ fmap onStm   where     onStm (Let pat aux e) =@@ -127,15 +127,15 @@ -- | Add a statement with the given pattern and expression. letBind ::   MonadBinder m =>-  Pattern (Lore m) ->-  Exp (Lore m) ->+  Pattern (Rep m) ->+  Exp (Rep m) ->   m () letBind pat e =   addStm =<< Let pat <$> (defAux <$> mkExpDecM pat e) <*> pure e  -- | Construct a 'Stm' from identifiers for the context- and value -- part of the pattern, as well as the expression.-mkLet :: Bindable lore => [Ident] -> [Ident] -> Exp lore -> Stm lore+mkLet :: Bindable rep => [Ident] -> [Ident] -> Exp rep -> Stm rep mkLet ctx val e =   let pat = mkExpPat ctx val e       dec = mkExpDec pat e@@ -143,7 +143,7 @@  -- | Like mkLet, but also take attributes and certificates from the -- given 'StmAux'.-mkLet' :: Bindable lore => [Ident] -> [Ident] -> StmAux a -> Exp lore -> Stm lore+mkLet' :: Bindable rep => [Ident] -> [Ident] -> StmAux a -> Exp rep -> Stm rep mkLet' ctx val (StmAux cs attrs _) e =   let pat = mkExpPat ctx val e       dec = mkExpDec pat e@@ -151,23 +151,23 @@  -- | Add a statement with the given pattern element names and -- expression.-letBindNames :: MonadBinder m => [VName] -> Exp (Lore m) -> m ()+letBindNames :: MonadBinder m => [VName] -> Exp (Rep m) -> m () letBindNames names e = addStm =<< mkLetNamesM names e  -- | As 'collectStms', but throw away the ordinary result.-collectStms_ :: MonadBinder m => m a -> m (Stms (Lore m))+collectStms_ :: MonadBinder m => m a -> m (Stms (Rep m)) collectStms_ = fmap snd . collectStms  -- | Add the statements of the body, then return the body result.-bodyBind :: MonadBinder m => Body (Lore m) -> m [SubExp]+bodyBind :: MonadBinder m => Body (Rep m) -> m [SubExp] bodyBind (Body _ stms es) = do   addStms stms   return es  -- | Add several bindings at the outermost level of a t'Body'.-insertStms :: Bindable lore => Stms lore -> Body lore -> Body lore+insertStms :: Bindable rep => Stms rep -> Body rep -> Body rep insertStms stms1 (Body _ stms2 res) = mkBody (stms1 <> stms2) res  -- | Add a single binding at the outermost level of a t'Body'.-insertStm :: Bindable lore => Stm lore -> Body lore -> Body lore+insertStm :: Bindable rep => Stm rep -> Body rep -> Body rep insertStm = insertStms . oneStm