futhark 0.15.7 → 0.15.8

raw patch · 251 files changed

+17588/−16693 lines, 251 filesdep −data-binary-ieee754binary-addedPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies removed: data-binary-ieee754

API changes (from Hackage documentation)

Files

• assets/ohyes.png binary
• docs/c-api.rst +1/−1
• docs/conf.py +1/−1
• docs/hacking.rst +13/−9
• docs/language-reference.rst +84/−3
• futhark.cabal +72/−57
• rts/c/values.h +16/−5
• src/Futhark/Actions.hs +7/−7
• src/Futhark/Analysis/AlgSimplify.hs +5/−11
• src/Futhark/Analysis/Alias.hs +20/−20
• src/Futhark/Analysis/CallGraph.hs +24/−1
• src/Futhark/Analysis/DataDependencies.hs +10/−4
• src/Futhark/Analysis/HORep/MapNest.hs +156/−0
• src/Futhark/Analysis/HORep/SOAC.hs +637/−0
• src/Futhark/Analysis/HORepresentation/MapNest.hs +0/−155
• src/Futhark/Analysis/HORepresentation/SOAC.hs +0/−637
• src/Futhark/Analysis/Metrics.hs +25/−12
• src/Futhark/Analysis/PrimExp.hs +5/−3
• src/Futhark/Analysis/PrimExp/Convert.hs +28/−42
• src/Futhark/Analysis/PrimExp/Generalize.hs +3/−3
• src/Futhark/Analysis/PrimExp/Simplify.hs +1/−1
• src/Futhark/Analysis/Range.hs +22/−18
• src/Futhark/Analysis/Rephrase.hs +25/−12
• src/Futhark/Analysis/ScalExp.hs +9/−4
• src/Futhark/Analysis/SymbolTable.hs +52/−52
• src/Futhark/Analysis/Usage.hs +0/−37
• src/Futhark/Analysis/UsageTable.hs +52/−17
• src/Futhark/Bench.hs +7/−1
• src/Futhark/Binder.hs +20/−31
• src/Futhark/Binder/Class.hs +66/−41
• src/Futhark/CLI/Dataset.hs +1/−2
• src/Futhark/CLI/Dev.hs +22/−22
• src/Futhark/CLI/Query.hs +1/−1
• src/Futhark/CLI/REPL.hs +4/−5
• src/Futhark/CLI/Run.hs +1/−2
• src/Futhark/CodeGen/Backends/CCUDA.hs +2/−1
• src/Futhark/CodeGen/Backends/CCUDA/Boilerplate.hs +3/−0
• src/Futhark/CodeGen/Backends/COpenCL.hs +3/−1
• src/Futhark/CodeGen/Backends/COpenCL/Boilerplate.hs +2/−0
• src/Futhark/CodeGen/Backends/CSOpenCL.hs +1/−1
• src/Futhark/CodeGen/Backends/GenericC.hs +4/−3
• src/Futhark/CodeGen/Backends/GenericCSharp.hs +3/−3
• src/Futhark/CodeGen/Backends/GenericPython.hs +3/−3
• src/Futhark/CodeGen/Backends/PyOpenCL.hs +1/−1
• src/Futhark/CodeGen/Backends/PyOpenCL/Boilerplate.hs +1/−0
• src/Futhark/CodeGen/Backends/SequentialC.hs +1/−1
• src/Futhark/CodeGen/Backends/SequentialCSharp.hs +1/−1
• src/Futhark/CodeGen/Backends/SequentialPython.hs +1/−1
• src/Futhark/CodeGen/Backends/SimpleRep.hs +759/−0
• src/Futhark/CodeGen/Backends/SimpleRepresentation.hs +0/−758
• src/Futhark/CodeGen/ImpCode.hs +62/−10
• src/Futhark/CodeGen/ImpCode/Kernels.hs +16/−5
• src/Futhark/CodeGen/ImpCode/OpenCL.hs +2/−2
• src/Futhark/CodeGen/ImpGen.hs +23/−23
• src/Futhark/CodeGen/ImpGen/CUDA.hs +1/−1
• src/Futhark/CodeGen/ImpGen/Kernels.hs +2/−2
• src/Futhark/CodeGen/ImpGen/Kernels/Base.hs +13/−11
• src/Futhark/CodeGen/ImpGen/Kernels/SegHist.hs +7/−6
• src/Futhark/CodeGen/ImpGen/Kernels/SegMap.hs +1/−1
• src/Futhark/CodeGen/ImpGen/Kernels/SegRed.hs +3/−3
• src/Futhark/CodeGen/ImpGen/Kernels/SegScan.hs +3/−3
• src/Futhark/CodeGen/ImpGen/Kernels/ToOpenCL.hs +1/−1
• src/Futhark/CodeGen/ImpGen/Kernels/Transpose.hs +31/−29
• src/Futhark/CodeGen/ImpGen/OpenCL.hs +1/−1
• src/Futhark/CodeGen/ImpGen/Sequential.hs +3/−1
• src/Futhark/CodeGen/OpenCL/Heuristics.hs +11/−12
• src/Futhark/CodeGen/SetDefaultSpace.hs +4/−0
• src/Futhark/Compiler.hs +7/−6
• src/Futhark/Compiler/CLI.hs +2/−2
• src/Futhark/Compiler/Program.hs +2/−3
• src/Futhark/Construct.hs +78/−15
• src/Futhark/Doc/Generator.hs +40/−4
• src/Futhark/Doc/Html.hs +0/−49
• src/Futhark/Error.hs +14/−0
• src/Futhark/IR.hs +17/−0
• src/Futhark/IR/Aliases.hs +359/−0
• src/Futhark/IR/Decorations.hs +52/−0
• src/Futhark/IR/Kernels.hs +58/−0
• src/Futhark/IR/Kernels/Kernel.hs +347/−0
• src/Futhark/IR/Kernels/Simplify.hs +97/−0
• src/Futhark/IR/Kernels/Sizes.hs +69/−0
• src/Futhark/IR/KernelsMem.hs +96/−0
• src/Futhark/IR/Mem.hs +997/−0
• src/Futhark/IR/Mem/IxFun.hs +849/−0
• src/Futhark/IR/Mem/Simplify.hs +216/−0
• src/Futhark/IR/Pretty.hs +295/−0
• src/Futhark/IR/Primitive.hs +1292/−0
• src/Futhark/IR/Prop.hs +223/−0
• src/Futhark/IR/Prop/Aliases.hs +182/−0
• src/Futhark/IR/Prop/Constants.hs +76/−0
• src/Futhark/IR/Prop/Names.hs +334/−0
• src/Futhark/IR/Prop/Patterns.hs +101/−0
• src/Futhark/IR/Prop/Ranges.hs +282/−0
• src/Futhark/IR/Prop/Rearrange.hs +108/−0
• src/Futhark/IR/Prop/Reshape.hs +177/−0
• src/Futhark/IR/Prop/Scope.hs +227/−0
• src/Futhark/IR/Prop/TypeOf.hs +156/−0
• src/Futhark/IR/Prop/Types.hs +550/−0
• src/Futhark/IR/Ranges.hs +187/−0
• src/Futhark/IR/RetType.hs +84/−0
• src/Futhark/IR/SOACS.hs +79/−0
• src/Futhark/IR/SOACS/SOAC.hs +791/−0
• src/Futhark/IR/SOACS/Simplify.hs +790/−0
• src/Futhark/IR/SegOp.hs +1177/−0
• src/Futhark/IR/Seq.hs +63/−0
• src/Futhark/IR/SeqMem.hs +83/−0
• src/Futhark/IR/Syntax.hs +534/−0
• src/Futhark/IR/Syntax/Core.hs +363/−0
• src/Futhark/IR/Traversals.hs +279/−0
• src/Futhark/Internalise.hs +27/−19
• src/Futhark/Internalise/AccurateSizes.hs +2/−14
• src/Futhark/Internalise/Bindings.hs +3/−3
• src/Futhark/Internalise/Defunctionalise.hs +23/−18
• src/Futhark/Internalise/Defunctorise.hs +4/−3
• src/Futhark/Internalise/Lambdas.hs +4/−6
• src/Futhark/Internalise/Monad.hs +6/−4
• src/Futhark/Internalise/Monomorphise.hs +37/−35
• src/Futhark/Internalise/TypesValues.hs +2/−1
• src/Futhark/MonadFreshNames.hs +3/−3
• src/Futhark/Optimise/CSE.hs +36/−36
• src/Futhark/Optimise/DoubleBuffer.hs +8/−7
• src/Futhark/Optimise/Fusion.hs +48/−42
• src/Futhark/Optimise/Fusion/Composing.hs +3/−3
• src/Futhark/Optimise/Fusion/LoopKernel.hs +17/−14
• src/Futhark/Optimise/InPlaceLowering.hs +20/−20
• src/Futhark/Optimise/InPlaceLowering/LowerIntoStm.hs +72/−57
• src/Futhark/Optimise/InPlaceLowering/SubstituteIndices.hs +32/−31
• src/Futhark/Optimise/InliningDeadFun.hs +57/−52
• src/Futhark/Optimise/Simplify.hs +2/−3
• src/Futhark/Optimise/Simplify/ClosedForm.hs +13/−12
• src/Futhark/Optimise/Simplify/Engine.hs +47/−58
• src/Futhark/Optimise/Simplify/Lore.hs +49/−49
• src/Futhark/Optimise/Simplify/Rule.hs +9/−9
• src/Futhark/Optimise/Simplify/Rules.hs +93/−89
• src/Futhark/Optimise/Sink.hs +10/−9
• src/Futhark/Optimise/TileLoops.hs +11/−10
• src/Futhark/Optimise/Unstream.hs +2/−1
• src/Futhark/Pass.hs +10/−4
• src/Futhark/Pass/ExpandAllocations.hs +39/−41
• src/Futhark/Pass/ExplicitAllocations.hs +49/−60
• src/Futhark/Pass/ExplicitAllocations/Kernels.hs +6/−3
• src/Futhark/Pass/ExplicitAllocations/SegOp.hs +8/−8
• src/Futhark/Pass/ExplicitAllocations/Seq.hs +2/−2
• src/Futhark/Pass/ExtractKernels.hs +69/−34
• src/Futhark/Pass/ExtractKernels/BlockedKernel.hs +13/−13
• src/Futhark/Pass/ExtractKernels/DistributeNests.hs +48/−34
• src/Futhark/Pass/ExtractKernels/Distribution.hs +21/−15
• src/Futhark/Pass/ExtractKernels/ISRWIM.hs +9/−5
• src/Futhark/Pass/ExtractKernels/Interchange.hs +10/−10
• src/Futhark/Pass/ExtractKernels/Intragroup.hs +13/−12
• src/Futhark/Pass/ExtractKernels/StreamKernel.hs +14/−7
• src/Futhark/Pass/ExtractKernels/ToKernels.hs +6/−6
• src/Futhark/Pass/FirstOrderTransform.hs +23/−3
• src/Futhark/Pass/KernelBabysitting.hs +11/−13
• src/Futhark/Pass/ResolveAssertions.hs +4/−4
• src/Futhark/Pass/Simplify.hs +6/−6
• src/Futhark/Passes.hs +5/−5
• src/Futhark/Pipeline.hs +36/−17
• src/Futhark/Pkg/Info.hs +1/−0
• src/Futhark/Representation/AST.hs +0/−16
• src/Futhark/Representation/AST/Annotations.hs +0/−47
• src/Futhark/Representation/AST/Attributes.hs +0/−221
• src/Futhark/Representation/AST/Attributes/Aliases.hs +0/−170
• src/Futhark/Representation/AST/Attributes/Constants.hs +0/−76
• src/Futhark/Representation/AST/Attributes/Names.hs +0/−330
• src/Futhark/Representation/AST/Attributes/Patterns.hs +0/−101
• src/Futhark/Representation/AST/Attributes/Ranges.hs +0/−274
• src/Futhark/Representation/AST/Attributes/Rearrange.hs +0/−108
• src/Futhark/Representation/AST/Attributes/Reshape.hs +0/−175
• src/Futhark/Representation/AST/Attributes/Scope.hs +0/−217
• src/Futhark/Representation/AST/Attributes/TypeOf.hs +0/−169
• src/Futhark/Representation/AST/Attributes/Types.hs +0/−542
• src/Futhark/Representation/AST/Pretty.hs +0/−287
• src/Futhark/Representation/AST/RetType.hs +0/−92
• src/Futhark/Representation/AST/Syntax.hs +0/−392
• src/Futhark/Representation/AST/Syntax/Core.hs +0/−358
• src/Futhark/Representation/AST/Traversals.hs +0/−279
• src/Futhark/Representation/Aliases.hs +0/−362
• src/Futhark/Representation/Kernels.hs +0/−60
• src/Futhark/Representation/Kernels/Kernel.hs +0/−347
• src/Futhark/Representation/Kernels/Simplify.hs +0/−100
• src/Futhark/Representation/Kernels/Sizes.hs +0/−66
• src/Futhark/Representation/KernelsMem.hs +0/−96
• src/Futhark/Representation/Mem.hs +0/−997
• src/Futhark/Representation/Mem/IxFun.hs +0/−841
• src/Futhark/Representation/Mem/Simplify.hs +0/−216
• src/Futhark/Representation/Primitive.hs +0/−1277
• src/Futhark/Representation/Ranges.hs +0/−183
• src/Futhark/Representation/SOACS.hs +0/−81
• src/Futhark/Representation/SOACS/SOAC.hs +0/−763
• src/Futhark/Representation/SOACS/Simplify.hs +0/−793
• src/Futhark/Representation/SegOp.hs +0/−1173
• src/Futhark/Representation/Seq.hs +0/−67
• src/Futhark/Representation/SeqMem.hs +0/−83
• src/Futhark/Test.hs +14/−3
• src/Futhark/Test/Values.hs +14/−13
• src/Futhark/Tools.hs +23/−37
• src/Futhark/Transform/CopyPropagate.hs +1/−1
• src/Futhark/Transform/FirstOrderTransform.hs +24/−22
• src/Futhark/Transform/Rename.hs +29/−32
• src/Futhark/Transform/Substitute.hs +37/−30
• src/Futhark/TypeCheck.hs +50/−44
• src/Futhark/Util.hs +10/−4
• src/Futhark/Util/Loc.hs +5/−0
• src/Futhark/Util/Log.hs +1/−0
• src/Futhark/Util/Pretty.hs +1/−0
• src/Futhark/Version.hs +1/−0
• src/Language/Futhark.hs +3/−2
• src/Language/Futhark/Attributes.hs +0/−1048
• src/Language/Futhark/Core.hs +6/−8
• src/Language/Futhark/Interpreter.hs +15/−5
• src/Language/Futhark/Parser.hs +2/−1
• src/Language/Futhark/Parser/Lexer.x +7/−2
• src/Language/Futhark/Parser/Parser.y +11/−3
• src/Language/Futhark/Prelude.hs +1/−0
• src/Language/Futhark/Pretty.hs +9/−2
• src/Language/Futhark/Prop.hs +1056/−0
• src/Language/Futhark/Query.hs +1/−2
• src/Language/Futhark/Semantic.hs +4/−1
• src/Language/Futhark/Syntax.hs +69/−39
• src/Language/Futhark/Traversals.hs +5/−0
• src/Language/Futhark/TypeChecker.hs +1/−1
• src/Language/Futhark/TypeChecker/Modules.hs +1/−1
• src/Language/Futhark/TypeChecker/Monad.hs +47/−30
• src/Language/Futhark/TypeChecker/Terms.hs +68/−17
• src/Language/Futhark/TypeChecker/Types.hs +12/−1
• src/Language/Futhark/TypeChecker/Unify.hs +29/−3
• src/Language/Futhark/Warnings.hs +6/−1
• unittests/Futhark/Analysis/ScalExpTests.hs +1/−1
• unittests/Futhark/IR/Mem/IxFun/Alg.hs +153/−0
• unittests/Futhark/IR/Mem/IxFunTests.hs +371/−0
• unittests/Futhark/IR/Mem/IxFunWrapper.hs +55/−0
• unittests/Futhark/IR/PrimitiveTests.hs +61/−0
• unittests/Futhark/IR/Prop/RearrangeTests.hs +55/−0
• unittests/Futhark/IR/Prop/ReshapeTests.hs +93/−0
• unittests/Futhark/IR/PropTests.hs +16/−0
• unittests/Futhark/IR/Syntax/CoreTests.hs +67/−0
• unittests/Futhark/IR/SyntaxTests.hs +7/−0
• unittests/Futhark/Optimise/AlgSimplifyTests.hs +1/−1
• unittests/Futhark/Representation/AST/Attributes/RearrangeTests.hs +0/−55
• unittests/Futhark/Representation/AST/Attributes/ReshapeTests.hs +0/−93
• unittests/Futhark/Representation/AST/AttributesTests.hs +0/−16
• unittests/Futhark/Representation/AST/Syntax/CoreTests.hs +0/−67
• unittests/Futhark/Representation/AST/SyntaxTests.hs +0/−7
• unittests/Futhark/Representation/Mem/IxFun/Alg.hs +0/−153
• unittests/Futhark/Representation/Mem/IxFunTests.hs +0/−371
• unittests/Futhark/Representation/Mem/IxFunWrapper.hs +0/−55
• unittests/Futhark/Representation/PrimitiveTests.hs +0/−61
• unittests/Language/Futhark/CoreTests.hs +1/−1
• unittests/Language/Futhark/SyntaxTests.hs +1/−1
• unittests/futhark_tests.hs +8/−8

binary file changed (absent → 18462 bytes)

@@ -23,7 +23,7 @@ Context creation is parameterised by a configuration object.  Any changes to the configuration must be made *before* calling :c:func:`futhark_context_new`.  A configuration object must not be-freed while before any context objects for which it is used.  The same+freed before any context objects for which it is used.  The same configuration may be used for multiple concurrent contexts.  .. c:type:: struct futhark_context_config

@@ -65,7 +65,7 @@     # Get cabal file     cabal_file = open('../futhark.cabal', 'r').read()     # Extract version-    return re.search('version:[ ]*([^ ]*)', cabal_file).group(1)+    return re.search(r'^version:[ ]*([^ ]*)$', cabal_file, flags=re.MULTILINE).group(1)  version = get_version() # The full version, including alpha/beta/rc tags.

@@ -4,18 +4,22 @@ ===============================  The Futhark compiler is a significant body of code with a not entirely-straightforward design.  The main reference is the `documentation of-the compiler internals`_ that is automatically generated by Haddock.-If you feel that it is incomplete, or lacks an explanation, then feel-free to report it as an issue on the `GitHub page`_.  Documentation-bugs are bugs too.+straightforward design.  The main source of documentation is the+Haddock comments in the source code itself.  You can generate+hyperlinked reference documentation by running ``stack haddock`` or+``cabal haddock``, depending on your preference of build system.+There is also possibly-outdated `documentation on Hackage`_ -.. _`documentation of the compiler internals`: https://futhark-lang.org/haddock/+If you feel that the documentation is incomplete, or something lacks+an explanation, then feel free to report it as an issue on the `GitHub+page`_.  Documentation bugs are bugs too.++.. _`documentation on Hackage`: http://hackage.haskell.org/package/futhark .. _`GitHub page`: https://github.com/diku-dk/futhark -The Futhark compiler is built using `Stack`_.  It's a good idea to-familiarise yourself with how it works.  As a starting point, here are-a few hints:+The Futhark compiler is usually built using `Stack`_.  It's a good+idea to familiarise yourself with how it works.  As a starting point,+here are a few hints:    * When testing, pass ``--fast`` to ``stack`` to disable the GHC     optimiser.  This speeds up builds considerably (although it still

@@ -14,8 +14,8 @@ practice (for example by applying rules of operator precedence).  This reference describes only the language itself.  Documentation for-the basis library is `available elsewhere-<https://futhark-lang.org/docs/>`_.+the built-in prelude is `available elsewhere+<https://futhark-lang.org/docs/prelude>`_.  Identifiers and Keywords ------------------------@@ -436,6 +436,7 @@       : | "let" `id` `type_param`* `pat`+ [":" `type`] "=" `exp` "in" `exp`       : | "(" "\" `pat`+ [":" `type`] "->" `exp` ")"       : | "loop" `pat` [("=" `exp`)] `loopform` "do" `exp`+      : | "#[" attr "]" `exp`       : | "unsafe" `exp`       : | "assert" `atom` `atom`       : | `exp` "with" "[" `index` ("," `index`)* "]" "=" `exp`@@ -798,6 +799,13 @@  Numerical negation of ``x``, which must be of numeric type. +``#[attr] e``+.............++Apply the given attribute to the expression.  Attributes are an ad-hoc+and optional mechanism for providing extra information, directives, or+hints to the compiler.  See :ref:`attributes` for more information.+ ``unsafe e`` ............ @@ -808,6 +816,8 @@ the code is correct; eliding such checks can lead to memory corruption. +This construct is deprecated.  Use the ``#[unsafe]`` attribute instead.+ ``assert cond e`` ................. @@ -882,7 +892,7 @@  Equivalent to ``loop (pat = initial) for x in [0..1..<n] do loopbody``. -``loop pat = initial = while cond do loopbody``+``loop pat = initial while cond do loopbody`` ...............................................  1. Bind ``pat`` to the initial values given in ``initial``.@@ -1564,3 +1574,74 @@ In fact, a plain ``import "file"`` is equivalent to::    local open import "file"++.. _attributes:++Attributes+----------++.. productionlist::+   attr:   `id`++An expression can be prefixed with an attribute, written as+``#[attr]``.  This may affect how it is treated by the compiler or+other tools.  In no case will attributes affect or change the+*semantics* of a program, but it may affect how well it compiles (or+in some cases, whether it compiles at all).  Unknown attributes are+silently ignored.  Most have no effect in the interpreter.++Many attributes affect second-order array combinators (*SOACS*).+These must be applied to a fully saturated function application or+they will have no effect.  If two SOACs with contradictory attributes+are combined through fusion, it is unspecified which attributes take+precedence.++The following expression attributes are supported.++``incremental_flattening_no_outer``+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~++When using incremental flattening, do not generate the "only outer+parallelism" version for the attributed SOACs.++``incremental_flattening_no_intra``+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~++When using incremental flattening, do not generate the "intra-group+parallelism" version for the attributed SOACs.++``incremental_flattening_only_inner``+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~++When using incremental flattening, do not generate multiple versions+for this SOAC, but do exploit inner parallelism (which may give rise+to multiple versions at deeper levels).++``noinline``+~~~~~~~~~~~~++Do not inline the attributed function application.  If used within a+parallel construct (e.g. ``map``), this will likely prevent the GPU+backends from generating working code.++``sequential``+~~~~~~~~~~~~~~++*Fully* sequentialise the attributed SOAC.++``sequential_outer``+~~~~~~~~~~~~~~~~~~~~++Turn the outer parallelism in the attributed SOAC sequential, but+preserve any inner parallelism.++``sequential_inner``+~~~~~~~~~~~~~~~~~~~~++Exploit only outer parallelism in the attributed SOAC.++``unsafe``+~~~~~~~~~~++Do not perform any dynamic safety checks (such as bound checks) during+execution of the attributed expression.

@@ -1,8 +1,9 @@ cabal-version: 2.4  name:           futhark-version:        0.15.7+version:        0.15.8 synopsis:       An optimising compiler for a functional, array-oriented language.+ description:    Futhark is a small programming language designed to be compiled to                 efficient parallel code. It is a statically typed, data-parallel,                 and purely functional array language in the ML family, and comes@@ -11,6 +12,20 @@                 is hardware-agnostic.                 .                 For more information, see the website at https://futhark-lang.org+                .+                For introductionary information about hacking on the+                Futhark compiler, see+                <https://futhark.readthedocs.io/en/latest/hacking.html the hacking guide>.+                Regarding the internal design of the compiler, the following modules make+                good starting points:+                .+                * "Futhark.IR.Syntax" explains the+                  basic design of the intermediate representation (IR).+                * "Futhark.Construct" explains how to write code that+                  manipulates and creates AST fragments.+                .+                <<assets/ohyes.png You too can go fast once you rewrite your program in Futhark.>>+ category:       Language homepage:       https://futhark-lang.org bug-reports:    https://github.com/diku-dk/futhark/issues@@ -29,6 +44,8 @@     docs/Makefile     docs/conf.py     docs/requirements.txt+extra-doc-files:+  assets/*.png  source-repository head   type: git@@ -41,8 +58,8 @@       Futhark.Analysis.Alias       Futhark.Analysis.CallGraph       Futhark.Analysis.DataDependencies-      Futhark.Analysis.HORepresentation.MapNest-      Futhark.Analysis.HORepresentation.SOAC+      Futhark.Analysis.HORep.MapNest+      Futhark.Analysis.HORep.SOAC       Futhark.Analysis.Metrics       Futhark.Analysis.PrimExp       Futhark.Analysis.PrimExp.Convert@@ -52,7 +69,6 @@       Futhark.Analysis.Rephrase       Futhark.Analysis.ScalExp       Futhark.Analysis.SymbolTable-      Futhark.Analysis.Usage       Futhark.Analysis.UsageTable       Futhark.Bench       Futhark.Binder@@ -60,10 +76,10 @@       Futhark.CLI.Autotune       Futhark.CLI.Bench       Futhark.CLI.C-      Futhark.CLI.Check-      Futhark.CLI.CSharp       Futhark.CLI.CSOpenCL+      Futhark.CLI.CSharp       Futhark.CLI.CUDA+      Futhark.CLI.Check       Futhark.CLI.Datacmp       Futhark.CLI.Dataset       Futhark.CLI.Dev@@ -98,7 +114,7 @@       Futhark.CodeGen.Backends.SequentialC       Futhark.CodeGen.Backends.SequentialCSharp       Futhark.CodeGen.Backends.SequentialPython-      Futhark.CodeGen.Backends.SimpleRepresentation+      Futhark.CodeGen.Backends.SimpleRep       Futhark.CodeGen.ImpCode       Futhark.CodeGen.ImpCode.Kernels       Futhark.CodeGen.ImpCode.OpenCL@@ -122,9 +138,43 @@       Futhark.Compiler.Program       Futhark.Construct       Futhark.Doc.Generator-      Futhark.Doc.Html       Futhark.Error       Futhark.FreshNames+      Futhark.IR+      Futhark.IR.Aliases+      Futhark.IR.Decorations+      Futhark.IR.Kernels+      Futhark.IR.Kernels.Kernel+      Futhark.IR.Kernels.Simplify+      Futhark.IR.Kernels.Sizes+      Futhark.IR.KernelsMem+      Futhark.IR.Mem+      Futhark.IR.Mem.IxFun+      Futhark.IR.Mem.Simplify+      Futhark.IR.Pretty+      Futhark.IR.Primitive+      Futhark.IR.Prop+      Futhark.IR.Prop.Aliases+      Futhark.IR.Prop.Constants+      Futhark.IR.Prop.Names+      Futhark.IR.Prop.Patterns+      Futhark.IR.Prop.Ranges+      Futhark.IR.Prop.Rearrange+      Futhark.IR.Prop.Reshape+      Futhark.IR.Prop.Scope+      Futhark.IR.Prop.TypeOf+      Futhark.IR.Prop.Types+      Futhark.IR.Ranges+      Futhark.IR.RetType+      Futhark.IR.SOACS+      Futhark.IR.SOACS.SOAC+      Futhark.IR.SOACS.Simplify+      Futhark.IR.SegOp+      Futhark.IR.Seq+      Futhark.IR.SeqMem+      Futhark.IR.Syntax+      Futhark.IR.Syntax.Core+      Futhark.IR.Traversals       Futhark.Internalise       Futhark.Internalise.AccurateSizes       Futhark.Internalise.Bindings@@ -140,10 +190,10 @@       Futhark.Optimise.Fusion       Futhark.Optimise.Fusion.Composing       Futhark.Optimise.Fusion.LoopKernel-      Futhark.Optimise.InliningDeadFun       Futhark.Optimise.InPlaceLowering       Futhark.Optimise.InPlaceLowering.LowerIntoStm       Futhark.Optimise.InPlaceLowering.SubstituteIndices+      Futhark.Optimise.InliningDeadFun       Futhark.Optimise.Simplify       Futhark.Optimise.Simplify.ClosedForm       Futhark.Optimise.Simplify.Engine@@ -163,9 +213,9 @@       Futhark.Pass.ExtractKernels.BlockedKernel       Futhark.Pass.ExtractKernels.DistributeNests       Futhark.Pass.ExtractKernels.Distribution+      Futhark.Pass.ExtractKernels.ISRWIM       Futhark.Pass.ExtractKernels.Interchange       Futhark.Pass.ExtractKernels.Intragroup-      Futhark.Pass.ExtractKernels.ISRWIM       Futhark.Pass.ExtractKernels.StreamKernel       Futhark.Pass.ExtractKernels.ToKernels       Futhark.Pass.FirstOrderTransform@@ -177,41 +227,6 @@       Futhark.Pkg.Info       Futhark.Pkg.Solve       Futhark.Pkg.Types-      Futhark.Representation.Aliases-      Futhark.Representation.AST-      Futhark.Representation.AST.Annotations-      Futhark.Representation.AST.Attributes-      Futhark.Representation.AST.Attributes.Aliases-      Futhark.Representation.AST.Attributes.Constants-      Futhark.Representation.AST.Attributes.Names-      Futhark.Representation.AST.Attributes.Patterns-      Futhark.Representation.AST.Attributes.Ranges-      Futhark.Representation.AST.Attributes.Rearrange-      Futhark.Representation.AST.Attributes.Reshape-      Futhark.Representation.AST.Attributes.Scope-      Futhark.Representation.AST.Attributes.TypeOf-      Futhark.Representation.AST.Attributes.Types-      Futhark.Representation.AST.Pretty-      Futhark.Representation.AST.RetType-      Futhark.Representation.AST.Syntax-      Futhark.Representation.AST.Syntax.Core-      Futhark.Representation.AST.Traversals-      Futhark.Representation.Mem-      Futhark.Representation.Mem.IxFun-      Futhark.Representation.Mem.Simplify-      Futhark.Representation.Kernels-      Futhark.Representation.Kernels.Kernel-      Futhark.Representation.Kernels.Simplify-      Futhark.Representation.Kernels.Sizes-      Futhark.Representation.KernelsMem-      Futhark.Representation.Primitive-      Futhark.Representation.Ranges-      Futhark.Representation.SegOp-      Futhark.Representation.Seq-      Futhark.Representation.SeqMem-      Futhark.Representation.SOACS-      Futhark.Representation.SOACS.Simplify-      Futhark.Representation.SOACS.SOAC       Futhark.Test       Futhark.Test.Values       Futhark.Tools@@ -223,18 +238,19 @@       Futhark.Util       Futhark.Util.Console       Futhark.Util.IntegralExp+      Futhark.Util.Loc       Futhark.Util.Log       Futhark.Util.Options       Futhark.Util.Pretty       Futhark.Util.Table       Futhark.Version       Language.Futhark-      Language.Futhark.Attributes       Language.Futhark.Core-      Language.Futhark.Prelude       Language.Futhark.Interpreter       Language.Futhark.Parser+      Language.Futhark.Prelude       Language.Futhark.Pretty+      Language.Futhark.Prop       Language.Futhark.Query       Language.Futhark.Semantic       Language.Futhark.Syntax@@ -267,7 +283,6 @@     , blaze-html >=0.9.0.1     , bytestring >=0.10.8     , containers >=0.6.2.1-    , data-binary-ieee754 >=0.1     , directory >=1.3.0.0     , directory-tree >=0.12.1     , dlist >=0.6.0.1@@ -322,15 +337,15 @@       Futhark.BenchTests       Futhark.Optimise.AlgSimplifyTests       Futhark.Pkg.SolveTests-      Futhark.Representation.AST.Attributes.RearrangeTests-      Futhark.Representation.AST.Attributes.ReshapeTests-      Futhark.Representation.AST.AttributesTests-      Futhark.Representation.AST.Syntax.CoreTests-      Futhark.Representation.AST.SyntaxTests-      Futhark.Representation.Mem.IxFun.Alg-      Futhark.Representation.Mem.IxFunTests-      Futhark.Representation.Mem.IxFunWrapper-      Futhark.Representation.PrimitiveTests+      Futhark.IR.Prop.RearrangeTests+      Futhark.IR.Prop.ReshapeTests+      Futhark.IR.PropTests+      Futhark.IR.Syntax.CoreTests+      Futhark.IR.SyntaxTests+      Futhark.IR.Mem.IxFun.Alg+      Futhark.IR.Mem.IxFunTests+      Futhark.IR.Mem.IxFunWrapper+      Futhark.IR.PrimitiveTests       Language.Futhark.CoreTests       Language.Futhark.SyntaxTests       Paths_futhark

@@ -2,7 +2,7 @@  //// Text I/O -typedef int (*writer)(FILE*, void*);+typedef int (*writer)(FILE*, const void*); typedef int (*bin_reader)(void*); typedef int (*str_reader)(const char *, void*); @@ -662,7 +662,11 @@   } } -static int write_str_array(FILE *out, const struct primtype_info_t *elem_type, unsigned char *data, int64_t *shape, int8_t rank) {+static int write_str_array(FILE *out,+                           const struct primtype_info_t *elem_type,+                           const unsigned char *data,+                           const int64_t *shape,+                           int8_t rank) {   if (rank==0) {     elem_type->write_str(out, (void*)data);   } else {@@ -704,7 +708,11 @@   return 0; } -static int write_bin_array(FILE *out, const struct primtype_info_t *elem_type, unsigned char *data, int64_t *shape, int8_t rank) {+static int write_bin_array(FILE *out,+                           const struct primtype_info_t *elem_type,+                           const unsigned char *data,+                           const int64_t *shape,+                           int8_t rank) {   int64_t num_elems = 1;   for (int64_t i = 0; i < rank; i++) {     num_elems *= shape[i];@@ -720,7 +728,7 @@    if (IS_BIG_ENDIAN) {     for (int64_t i = 0; i < num_elems; i++) {-      unsigned char *elem = data+i*elem_type->size;+      const unsigned char *elem = data+i*elem_type->size;       for (int64_t j = 0; j < elem_type->size; j++) {         fwrite(&elem[elem_type->size-j], 1, 1, out);       }@@ -733,7 +741,10 @@ }  static int write_array(FILE *out, int write_binary,-                       const struct primtype_info_t *elem_type, void *data, int64_t *shape, int8_t rank) {+                       const struct primtype_info_t *elem_type,+                       const void *data,+                       const int64_t *shape,+                       const int8_t rank) {   if (write_binary) {     return write_bin_array(out, elem_type, data, shape, rank);   } else {

@@ -16,17 +16,17 @@ import Futhark.Pipeline import Futhark.Analysis.Alias import Futhark.Analysis.Range-import Futhark.Representation.AST-import Futhark.Representation.AST.Attributes.Aliases-import Futhark.Representation.KernelsMem (KernelsMem)-import Futhark.Representation.SeqMem (SeqMem)+import Futhark.IR+import Futhark.IR.Prop.Aliases+import Futhark.IR.KernelsMem (KernelsMem)+import Futhark.IR.SeqMem (SeqMem) import qualified Futhark.CodeGen.ImpGen.Sequential as ImpGenSequential import qualified Futhark.CodeGen.ImpGen.Kernels as ImpGenKernels-import Futhark.Representation.AST.Attributes.Ranges (CanBeRanged)+import Futhark.IR.Prop.Ranges (CanBeRanged) import Futhark.Analysis.Metrics  -- | Print the result to stdout, with alias annotations.-printAction :: (Attributes lore, CanBeAliased (Op lore)) => Action lore+printAction :: (ASTLore lore, CanBeAliased (Op lore)) => Action lore printAction =   Action { actionName = "Prettyprint"          , actionDescription = "Prettyprint the resulting internal representation on standard output."@@ -34,7 +34,7 @@          }  -- | Print the result to stdout, with range annotations.-rangeAction :: (Attributes lore, CanBeRanged (Op lore)) => Action lore+rangeAction :: (ASTLore lore, CanBeRanged (Op lore)) => Action lore rangeAction =     Action { actionName = "Range analysis"            , actionDescription = "Print the program with range annotations added."

@@ -1,4 +1,5 @@ {-# LANGUAGE FlexibleInstances, LambdaCase #-}+-- | Algebraic simplification.  Slow and limited.  Use very rarely. module Futhark.Analysis.AlgSimplify   ( ScalExp   , Error@@ -18,9 +19,9 @@ import Control.Monad.Reader import Control.Monad.State -import Futhark.Representation.AST hiding (SDiv, SMod, SQuot, SRem, SSignum)+import Futhark.IR hiding (SDiv, SMod, SQuot, SRem, SSignum) import Futhark.Analysis.ScalExp-import qualified Futhark.Representation.Primitive as P+import qualified Futhark.IR.Primitive as P  -- | Ranges are inclusive. type RangesRep = M.Map VName (Int, Maybe ScalExp, Maybe ScalExp)@@ -49,6 +50,7 @@                                      -- too much time.                                      } +-- | Why the algebraic simplification failed. data Error = StepsExceeded | Error String  type AlgSimplifyM = StateT Int (ReaderT AlgSimplifyEnv (Either Error))@@ -445,17 +447,9 @@             e_num <- toNumSofP e_num_scal             gaussAllLTH0 only_static elsyms0 e_num ---    pos <- asks pos---    badAlgSimplifyM "gaussOneDefaultLTH0: unimplemented!"---------------------------------------------------------------- Pick a Symbol to Eliminate & Bring To Linear Form  ---------------------------------------------------------------+-- | Pick a Symbol to Eliminate & Bring To Linear Form pickSymToElim :: RangesRep -> S.Set VName -> ScalExp -> Maybe VName pickSymToElim rangesrep elsyms0 e_scal =---    ranges <- asks ranges---    e_scal <- fromNumSofP e0     let ids0= namesToList $ freeIn e_scal         ids1= filter (\s -> not (S.member s elsyms0)) ids0         ids2= filter (\s -> case M.lookup s rangesrep of

@@ -3,8 +3,8 @@ -- program with an arbitrary lore and produces one with aliases.  This -- module does not implement the aliasing logic itself, and derives -- its information from definitions in--- "Futhark.Representation.AST.Attributes.Aliases" and--- "Futhark.Representation.Aliases".  The alias information computed+-- "Futhark.IR.Prop.Aliases" and+-- "Futhark.IR.Aliases".  The alias information computed -- here will include transitive aliases (note that this is not what -- the building blocks do). module Futhark.Analysis.Alias@@ -22,16 +22,16 @@ import Data.List (foldl') import qualified Data.Map as M -import Futhark.Representation.AST.Syntax-import Futhark.Representation.Aliases+import Futhark.IR.Syntax+import Futhark.IR.Aliases  -- | Perform alias analysis on a Futhark program.-aliasAnalysis :: (Attributes lore, CanBeAliased (Op lore)) =>+aliasAnalysis :: (ASTLore lore, CanBeAliased (Op lore)) =>                  Prog lore -> Prog (Aliases lore) aliasAnalysis (Prog consts funs) =   Prog (fst (analyseStms mempty consts)) (map analyseFun funs) -analyseFun :: (Attributes lore, CanBeAliased (Op lore)) =>+analyseFun :: (ASTLore lore, CanBeAliased (Op lore)) =>               FunDef lore -> FunDef (Aliases lore) analyseFun (FunDef entry fname restype params body) =   FunDef entry fname restype params body'@@ -41,14 +41,14 @@ -- aliases. type AliasTable = M.Map VName Names -analyseBody :: (Attributes lore,+analyseBody :: (ASTLore lore,                 CanBeAliased (Op lore)) =>                AliasTable -> Body lore -> Body (Aliases lore) analyseBody atable (Body lore stms result) =   let (stms', _atable') = analyseStms atable stms   in mkAliasedBody lore stms' result -analyseStms :: (Attributes lore, CanBeAliased (Op lore)) =>+analyseStms :: (ASTLore lore, CanBeAliased (Op lore)) =>                AliasTable -> Stms lore -> (Stms (Aliases lore), AliasesAndConsumed) analyseStms orig_aliases =   foldl' f (mempty, (orig_aliases, mempty)) . stmsToList@@ -57,22 +57,22 @@               atable' = trackAliases aliases stm'           in (stms<>oneStm stm', atable') -analyseStm :: (Attributes lore, CanBeAliased (Op lore)) =>+analyseStm :: (ASTLore lore, CanBeAliased (Op lore)) =>               AliasTable -> Stm lore -> Stm (Aliases lore)-analyseStm aliases (Let pat (StmAux cs attr) e) =+analyseStm aliases (Let pat (StmAux cs attrs dec) e) =   let e' = analyseExp aliases e       pat' = addAliasesToPattern pat e'-      lore' = (Names' $ consumedInExp e', attr)-  in Let pat' (StmAux cs lore') e'+      lore' = (Names' $ consumedInExp e', dec)+  in Let pat' (StmAux cs attrs lore') e' -analyseExp :: (Attributes lore, CanBeAliased (Op lore)) =>+analyseExp :: (ASTLore lore, CanBeAliased (Op lore)) =>               AliasTable -> Exp lore -> Exp (Aliases lore)  -- Would be better to put this in a BranchType annotation, but that -- requires a lot of other work.-analyseExp aliases (If cond tb fb attr) =-  let Body ((tb_als, tb_cons), tb_attr) tb_stms tb_res = analyseBody aliases tb-      Body ((fb_als, fb_cons), fb_attr) fb_stms fb_res = analyseBody aliases fb+analyseExp aliases (If cond tb fb dec) =+  let Body ((tb_als, tb_cons), tb_dec) tb_stms tb_res = analyseBody aliases tb+      Body ((fb_als, fb_cons), fb_dec) fb_stms fb_res = analyseBody aliases fb       cons = tb_cons <> fb_cons       isConsumed v = any (`nameIn` unNames cons) $                      v : namesToList (M.findWithDefault mempty v aliases)@@ -81,9 +81,9 @@                     namesToList . unNames       tb_als' = map notConsumed tb_als       fb_als' = map notConsumed fb_als-      tb' = Body ((tb_als', tb_cons), tb_attr) tb_stms tb_res-      fb' = Body ((fb_als', fb_cons), fb_attr) fb_stms fb_res-  in If cond tb' fb' attr+      tb' = Body ((tb_als', tb_cons), tb_dec) tb_stms tb_res+      fb' = Body ((fb_als', fb_cons), fb_dec) fb_stms fb_res+  in If cond tb' fb' dec  analyseExp aliases e = mapExp analyse e   where analyse =@@ -97,7 +97,7 @@                  , mapOnOp = return . addOpAliases                  } -analyseLambda :: (Attributes lore, CanBeAliased (Op lore)) =>+analyseLambda :: (ASTLore lore, CanBeAliased (Op lore)) =>                  Lambda lore -> Lambda (Aliases lore) analyseLambda lam =   -- XXX: it may cause trouble that we pass mempty to analyseBody

@@ -1,3 +1,4 @@+{-# LANGUAGE OverloadedStrings #-} -- | This module exports functionality for generating a call graph of -- an Futhark program. module Futhark.Analysis.CallGraph@@ -7,6 +8,7 @@   , calls   , calledByConsts   , allCalledBy+  , findNoninlined   )   where @@ -16,7 +18,7 @@ import Data.Maybe (fromMaybe) import Data.List (foldl') -import Futhark.Representation.SOACS+import Futhark.IR.SOACS  type FunctionTable = M.Map Name (FunDef SOACS) @@ -93,3 +95,24 @@           mapOnBody = \_ body -> do tell $ buildFGBody body                                     return body           }++-- | The set of all functions that are called noinline somewhere.+findNoninlined :: Prog SOACS -> S.Set Name+findNoninlined prog =+  foldMap onStm $ foldMap (bodyStms . funDefBody) (progFuns prog) <> progConsts prog+  where onStm :: Stm -> S.Set Name+        onStm (Let _ aux (Apply fname _ _ _))+          | "noinline" `inAttrs` stmAuxAttrs aux =+              S.singleton fname+        onStm (Let _ _ e) = execWriter $ mapExpM folder e+          where folder =+                  identityMapper+                  { mapOnBody = \_ body -> do tell $ foldMap onStm $ bodyStms body+                                              return body+                  , mapOnOp = mapSOACM+                              identitySOACMapper+                              { mapOnSOACLambda = \lam -> do+                                  tell $ foldMap onStm $ bodyStms $ lambdaBody lam+                                  return lam+                              }+                  }

@@ -9,7 +9,7 @@  import qualified Data.Map.Strict as M -import Futhark.Representation.AST+import Futhark.IR  -- | A mapping from a variable name @v@, to those variables on which -- the value of @v@ is dependent.  The intuition is that we could@@ -18,10 +18,10 @@ type Dependencies = M.Map VName Names  -- | Compute the data dependencies for an entire body.-dataDependencies :: Attributes lore => Body lore -> Dependencies+dataDependencies :: ASTLore lore => Body lore -> Dependencies dataDependencies = dataDependencies' M.empty -dataDependencies' :: Attributes lore =>+dataDependencies' :: ASTLore lore =>                      Dependencies -> Body lore -> Dependencies dataDependencies' startdeps = foldl grow startdeps . bodyStms   where grow deps (Let pat _ (If c tb fb _)) =@@ -50,7 +50,13 @@ depsOfVar :: Dependencies -> VName -> Names depsOfVar deps name = oneName name <> M.findWithDefault mempty name deps -findNecessaryForReturned :: (Param attr -> Bool) -> [(Param attr, SubExp)]+-- | @findNecessaryForReturned p merge deps@ computes which of the+-- loop parameters (@merge@) are necessary for the result of the loop,+-- where @p@ given a loop parameter indicates whether the final value+-- of that parameter is live after the loop.  @deps@ is the data+-- dependencies of the loop body.  This is computed by straightforward+-- fixpoint iteration.+findNecessaryForReturned :: (Param dec -> Bool) -> [(Param dec, SubExp)]                          -> M.Map VName Names                          -> Names findNecessaryForReturned usedAfterLoop merge_and_res allDependencies =

@@ -0,0 +1,156 @@+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE TupleSections #-}+module Futhark.Analysis.HORep.MapNest+  ( Nesting (..)+  , MapNest (..)+  , typeOf+  , params+  , inputs+  , setInputs+  , fromSOAC+  , toSOAC+  )+where++import Data.List (find)+import Data.Maybe+import qualified Data.Map.Strict as M++import qualified Futhark.Analysis.HORep.SOAC as SOAC+import Futhark.Analysis.HORep.SOAC (SOAC)+import qualified Futhark.IR.SOACS.SOAC as Futhark+import Futhark.Transform.Substitute+import Futhark.IR hiding (typeOf)+import Futhark.MonadFreshNames+import Futhark.Construct++data Nesting lore = Nesting {+    nestingParamNames   :: [VName]+  , nestingResult       :: [VName]+  , nestingReturnType   :: [Type]+  , nestingWidth        :: SubExp+  } deriving (Eq, Ord, Show)++data MapNest lore = MapNest SubExp (Lambda lore) [Nesting lore] [SOAC.Input]+                  deriving (Show)++typeOf :: MapNest lore -> [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 _ lam [] _)       =+  map paramName $ lambdaParams lam+params (MapNest _ _ (nest:_) _) =+  nestingParamNames nest++inputs :: MapNest lore -> [SOAC.Input]+inputs (MapNest _ _ _ inps) = inps++setInputs :: [SOAC.Input] -> MapNest lore -> MapNest lore+setInputs [] (MapNest w body ns _) = MapNest w body ns []+setInputs (inp:inps) (MapNest _ body ns _) = MapNest w body ns' (inp:inps)+  where w = arraySize 0 $ SOAC.inputType inp+        ws = drop 1 $ arrayDims $ SOAC.inputType inp+        ns' = zipWith setDepth ns ws+        setDepth n nw = n { nestingWidth = nw }++fromSOAC :: (Bindable lore, MonadFreshNames m,+             LocalScope lore m,+             Op lore ~ Futhark.SOAC lore) =>+            SOAC lore -> m (Maybe (MapNest lore))+fromSOAC = fromSOAC' mempty++fromSOAC' :: (Bindable lore, MonadFreshNames m,+              LocalScope lore m,+              Op lore ~ Futhark.SOAC lore) =>+             [Ident]+          -> SOAC lore+          -> m (Maybe (MapNest lore))++fromSOAC' bound (SOAC.Screma w (SOAC.ScremaForm [] [] lam) inps) = do+  maybenest <- case (stmsToList $ bodyStms $ lambdaBody lam,+                     bodyResult $ lambdaBody lam) of+    ([Let pat _ e], res) | res == map Var (patternNames pat) ->+      localScope (scopeOfLParams $ lambdaParams lam) $+      SOAC.fromExp e >>=+      either (return . Left) (fmap (Right . fmap (pat,)) . fromSOAC' bound')+    _ ->+      return $ Right Nothing++  case maybenest of+    -- Do we have a nested MapNest?+    Right (Just (pat, mn@(MapNest inner_w body' ns' inps'))) -> do+      (ps, inps'') <-+        unzip <$>+        fixInputs w (zip (map paramName $ lambdaParams lam) inps)+        (zip (params mn) inps')+      let n' = Nesting { nestingParamNames = ps+                       , nestingResult     = patternNames pat+                       , nestingReturnType = typeOf mn+                       , nestingWidth      = inner_w+                       }+      return $ Just $ MapNest w body' (n':ns') inps''+    -- No nested MapNest it seems.+    _ -> do+      let isBound name+            | Just param <- find ((name==) . identName) bound =+              Just param+            | otherwise =+              Nothing+          boundUsedInBody =+            mapMaybe isBound $ namesToList $ freeIn lam+      newParams <- mapM (newIdent' (++"_wasfree")) boundUsedInBody+      let subst = M.fromList $+                  zip (map identName boundUsedInBody) (map identName newParams)+          inps' = inps +++                  map (SOAC.addTransform (SOAC.Replicate mempty $ Shape [w]) . SOAC.identInput)+                  boundUsedInBody+          lam' =+            lam { lambdaBody =+                    substituteNames subst $ lambdaBody lam+                , lambdaParams =+                    lambdaParams lam ++ [ Param name t+                                        | Ident name t <- newParams ]+                }+      return $ Just $ MapNest w lam' [] inps'+  where bound' = bound <> map paramIdent (lambdaParams lam)++fromSOAC' _ _ = return Nothing++toSOAC :: (MonadFreshNames m, HasScope lore m,+           Bindable lore, BinderOps lore, Op lore ~ Futhark.SOAC lore) =>+          MapNest lore -> m (SOAC lore)+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+  let nparams = zipWith Param npnames $ map SOAC.inputRowType inps+  body <- runBodyBinder $ localScope (scopeOfLParams nparams) $ do+    letBindNames nres =<< SOAC.toExp =<<+      toSOAC (MapNest nw lam ns $ map (SOAC.identInput . paramIdent) nparams)+    return $ resultBody $ map Var nres+  let outerlam = Lambda { lambdaParams = nparams+                        , lambdaBody = body+                        , lambdaReturnType = nrettype+                        }+  return $ SOAC.Screma w (Futhark.mapSOAC outerlam) inps++fixInputs :: MonadFreshNames m =>+             SubExp -> [(VName, SOAC.Input)] -> [(VName, SOAC.Input)]+          -> m [(VName, SOAC.Input)]+fixInputs w ourInps = mapM inspect+  where+    isParam x (y, _) = x == y++    inspect (_, SOAC.Input ts v _)+      | Just (p,pInp) <- find (isParam v) ourInps = do+          let pInp' = SOAC.transformRows ts pInp+          p' <- newNameFromString $ baseString p+          return (p', pInp')++    inspect (param, SOAC.Input ts a t) = do+      param' <- newNameFromString (baseString param ++ "_rep")+      return (param', SOAC.Input (ts SOAC.|> SOAC.Replicate mempty (Shape [w])) a t)

@@ -0,0 +1,637 @@+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE FlexibleInstances #-}+-- | High-level representation of SOACs.  When performing+-- SOAC-transformations, operating on normal 'Exp' values is somewhat+-- of a nuisance, as they can represent terms that are not proper+-- SOACs.  In contrast, this module exposes a SOAC representation that+-- does not enable invalid representations (except for type errors).+--+-- Furthermore, while standard normalised Futhark requires that the inputs+-- to a SOAC are variables or constants, the representation in this+-- module also supports various index-space transformations, like+-- @replicate@ or @rearrange@.  This is also very convenient when+-- implementing transformations.+--+-- The names exported by this module conflict with the standard Futhark+-- syntax tree constructors, so you are advised to use a qualified+-- import:+--+-- @+-- import Futhark.Analysis.HORep.SOAC (SOAC)+-- import qualified Futhark.Analysis.HORep.SOAC as SOAC+-- @+module Futhark.Analysis.HORep.SOAC+  (+   -- * SOACs+    SOAC (..)+  , Futhark.ScremaForm(..)+  , inputs+  , setInputs+  , lambda+  , setLambda+  , typeOf+  , width+  -- ** Converting to and from expressions+  , NotSOAC (..)+  , fromExp+  , toExp+  , toSOAC+  -- * SOAC inputs+  , Input (..)+  , varInput+  , identInput+  , isVarInput+  , isVarishInput+  , addTransform+  , addInitialTransforms+  , inputArray+  , inputRank+  , inputType+  , inputRowType+  , transformRows+  , transposeInput+  -- ** Input transformations+  , ArrayTransforms+  , noTransforms+  , nullTransforms+  , (|>)+  , (<|)+  , viewf+  , ViewF(..)+  , viewl+  , ViewL(..)+  , ArrayTransform(..)+  , transformFromExp+  , soacToStream+  )+  where++import Data.Foldable as Foldable+import Data.Maybe+import qualified Data.Sequence as Seq++import qualified Futhark.IR as Futhark+import Futhark.IR.SOACS.SOAC+  (StreamForm(..), ScremaForm(..), scremaType, getStreamAccums, HistOp(..), StreamOrd(..))+import qualified Futhark.IR.SOACS.SOAC as Futhark+import Futhark.IR+  hiding (Var, Iota, Rearrange, Reshape, Replicate, typeOf)+import Futhark.Transform.Substitute+import Futhark.Construct hiding (toExp)+import Futhark.Transform.Rename (renameLambda)+import qualified Futhark.Util.Pretty as PP+import Futhark.Util.Pretty (ppr, text)++-- | A single, simple transformation.  If you want several, don't just+-- create a list, use 'ArrayTransforms' instead.+data ArrayTransform = Rearrange Certificates [Int]+                    -- ^ A permutation of an otherwise valid input.+                    | Reshape Certificates (ShapeChange SubExp)+                    -- ^ A reshaping of an otherwise valid input.+                    | ReshapeOuter Certificates (ShapeChange SubExp)+                    -- ^ A reshaping of the outer dimension.+                    | ReshapeInner Certificates (ShapeChange SubExp)+                    -- ^ A reshaping of everything but the outer dimension.+                    | Replicate Certificates Shape+                    -- ^ Replicate the rows of the array a number of times.+                      deriving (Show, Eq, Ord)++instance Substitute ArrayTransform where+  substituteNames substs (Rearrange cs xs) =+    Rearrange (substituteNames substs cs) xs+  substituteNames substs (Reshape cs ses) =+    Reshape (substituteNames substs cs) (substituteNames substs ses)+  substituteNames substs (ReshapeOuter cs ses) =+    ReshapeOuter (substituteNames substs cs) (substituteNames substs ses)+  substituteNames substs (ReshapeInner cs ses) =+    ReshapeInner (substituteNames substs cs) (substituteNames substs ses)+  substituteNames substs (Replicate cs se) =+    Replicate (substituteNames substs cs) (substituteNames substs se)++-- | A sequence of array transformations, heavily inspired by+-- "Data.Seq".  You can decompose it using 'viewf' and 'viewl', and+-- grow it by using '|>' and '<|'.  These correspond closely to the+-- similar operations for sequences, except that appending will try to+-- normalise and simplify the transformation sequence.+--+-- The data type is opaque in order to enforce normalisation+-- invariants.  Basically, when you grow the sequence, the+-- implementation will try to coalesce neighboring permutations, for+-- example by composing permutations and removing identity+-- transformations.+newtype ArrayTransforms = ArrayTransforms (Seq.Seq ArrayTransform)+  deriving (Eq, Ord, Show)++instance Semigroup ArrayTransforms where+  ts1 <> ts2 = case viewf ts2 of+                 t :< ts2' -> (ts1 |> t) <> ts2'+                 EmptyF    -> ts1++instance Monoid ArrayTransforms where+  mempty = noTransforms++instance Substitute ArrayTransforms where+  substituteNames substs (ArrayTransforms ts) =+    ArrayTransforms $ substituteNames substs <$> ts++-- | The empty transformation list.+noTransforms :: ArrayTransforms+noTransforms = ArrayTransforms Seq.empty++-- | Is it an empty transformation list?+nullTransforms :: ArrayTransforms -> Bool+nullTransforms (ArrayTransforms s) = Seq.null s++-- | Decompose the input-end of the transformation sequence.+viewf :: ArrayTransforms -> ViewF+viewf (ArrayTransforms s) = case Seq.viewl s of+                              t Seq.:< s' -> t :< ArrayTransforms s'+                              Seq.EmptyL  -> EmptyF++-- | A view of the first transformation to be applied.+data ViewF = EmptyF+           | ArrayTransform :< ArrayTransforms++-- | Decompose the output-end of the transformation sequence.+viewl :: ArrayTransforms -> ViewL+viewl (ArrayTransforms s) = case Seq.viewr s of+                              s' Seq.:> t -> ArrayTransforms s' :> t+                              Seq.EmptyR  -> EmptyL++-- | A view of the last transformation to be applied.+data ViewL = EmptyL+           | ArrayTransforms :> ArrayTransform++-- | Add a transform to the end of the transformation list.+(|>) :: ArrayTransforms -> ArrayTransform -> ArrayTransforms+(|>) = flip $ addTransform' extract add $ uncurry (flip (,))+   where extract ts' = case viewl ts' of+                         EmptyL     -> Nothing+                         ts'' :> t' -> Just (t', ts'')+         add t' (ArrayTransforms ts') = ArrayTransforms $ ts' Seq.|> t'++-- | Add a transform at the beginning of the transformation list.+(<|) :: ArrayTransform -> ArrayTransforms -> ArrayTransforms+(<|) = addTransform' extract add id+   where extract ts' = case viewf ts' of+                         EmptyF     -> Nothing+                         t' :< ts'' -> Just (t', ts'')+         add t' (ArrayTransforms ts') = ArrayTransforms $ t' Seq.<| ts'++addTransform' :: (ArrayTransforms -> Maybe (ArrayTransform, ArrayTransforms))+              -> (ArrayTransform -> ArrayTransforms -> ArrayTransforms)+              -> ((ArrayTransform,ArrayTransform) -> (ArrayTransform,ArrayTransform))+              -> ArrayTransform -> ArrayTransforms+              -> ArrayTransforms+addTransform' extract add swap t ts =+  fromMaybe (t `add` ts) $ do+    (t', ts') <- extract ts+    combined <- uncurry combineTransforms $ swap (t', t)+    Just $ if identityTransform combined then ts'+           else addTransform' extract add swap combined ts'++identityTransform :: ArrayTransform -> Bool+identityTransform (Rearrange _ perm) =+  Foldable.and $ zipWith (==) perm [0..]+identityTransform _ = False++combineTransforms :: ArrayTransform -> ArrayTransform -> Maybe ArrayTransform+combineTransforms (Rearrange cs2 perm2) (Rearrange cs1 perm1) =+  Just $ Rearrange (cs1<>cs2) $ perm2 `rearrangeCompose` perm1+combineTransforms _ _ = Nothing++-- | Given an expression, determine whether the expression represents+-- 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 cs (BasicOp (Futhark.Rearrange perm v)) =+  Just (v, Rearrange cs perm)+transformFromExp cs (BasicOp (Futhark.Reshape shape v)) =+  Just (v, Reshape cs shape)+transformFromExp cs (BasicOp (Futhark.Replicate shape (Futhark.Var v))) =+  Just (v, Replicate cs shape)+transformFromExp _ _ = Nothing++-- | One array input to a SOAC - a SOAC may have multiple inputs, but+-- all are of this form.  Only the array inputs are expressed with+-- this type; other arguments, such as initial accumulator values, are+-- plain expressions.  The transforms are done left-to-right, that is,+-- the first element of the 'ArrayTransform' list is applied first.+data Input = Input ArrayTransforms VName Type+             deriving (Show, Eq, Ord)++instance Substitute Input where+  substituteNames substs (Input ts v t) =+    Input (substituteNames substs ts)+    (substituteNames substs v) (substituteNames substs t)++-- | Create a plain array variable input with no transformations.+varInput :: HasScope t f => VName -> f Input+varInput v = withType <$> lookupType v+  where withType = Input (ArrayTransforms Seq.empty) v++-- | Create a plain array variable input with no transformations, from an 'Ident'.+identInput :: Ident -> Input+identInput v = Input (ArrayTransforms Seq.empty) (identName v) (identType v)++-- | If the given input is a plain variable input, with no transforms,+-- return the variable.+isVarInput :: Input -> Maybe VName+isVarInput (Input ts v _) | nullTransforms ts = Just v+isVarInput _                                  = Nothing++-- | If the given input is a plain variable input, with no non-vacuous transforms,+-- return the variable.+isVarishInput :: Input -> Maybe VName+isVarishInput (Input ts v t)+  | nullTransforms ts = Just v+  | Reshape cs [DimCoercion _] :< ts' <- viewf ts, cs == mempty =+      isVarishInput $ Input ts' v t+isVarishInput _ = Nothing++-- | Add a transformation to the end of the transformation list.+addTransform :: ArrayTransform -> Input -> Input+addTransform tr (Input trs a t) =+  Input (trs |> tr) a t++-- | Add several transformations to the start of the transformation+-- list.+addInitialTransforms :: ArrayTransforms -> Input -> Input+addInitialTransforms ts (Input ots a t) = Input (ts <> ots) a t++-- | Convert SOAC inputs to the corresponding expressions.+inputsToSubExps :: (MonadBinder m) =>+                   [Input] -> m [VName]+inputsToSubExps = mapM inputToExp'+  where inputToExp' (Input (ArrayTransforms ts) a _) =+          foldlM transform a ts++        transform ia (Replicate cs n) =+          certifying cs $+          letExp "repeat" $ BasicOp $ Futhark.Replicate n (Futhark.Var ia)++        transform ia (Rearrange cs perm) =+          certifying cs $+          letExp "rearrange" $ BasicOp $ Futhark.Rearrange perm ia++        transform ia (Reshape cs shape) =+          certifying cs $+          letExp "reshape" $ BasicOp $ Futhark.Reshape shape ia++        transform ia (ReshapeOuter cs shape) = do+          shape' <- reshapeOuter shape 1 . arrayShape <$> lookupType ia+          certifying cs $+            letExp "reshape_outer" $ BasicOp $ Futhark.Reshape shape' ia++        transform ia (ReshapeInner cs shape) = do+          shape' <- reshapeInner shape 1 . arrayShape <$> lookupType ia+          certifying cs $+            letExp "reshape_inner" $ BasicOp $ Futhark.Reshape shape' ia++-- | Return the array name of the input.+inputArray :: Input -> VName+inputArray (Input _ v _) = v++-- | Return the type of an input.+inputType :: Input -> Type+inputType (Input (ArrayTransforms ts) _ at) =+  Foldable.foldl transformType at ts+  where transformType t (Replicate _ shape) =+          arrayOfShape t shape+        transformType t (Rearrange _ perm) =+          rearrangeType perm t+        transformType t (Reshape _ shape) =+          t `setArrayShape` newShape shape+        transformType t (ReshapeOuter _ shape) =+          let Shape oldshape = arrayShape t+          in t `setArrayShape` Shape (newDims shape ++ drop 1 oldshape)+        transformType t (ReshapeInner _ shape) =+          let Shape oldshape = arrayShape t+          in t `setArrayShape` Shape (take 1 oldshape ++ newDims shape)++-- | Return the row type of an input.  Just a convenient alias.+inputRowType :: Input -> Type+inputRowType = rowType . inputType++-- | Return the array rank (dimensionality) of an input.  Just a+-- convenient alias.+inputRank :: Input -> Int+inputRank = arrayRank . inputType++-- | Apply the transformations to every row of the input.+transformRows :: ArrayTransforms -> Input -> Input+transformRows (ArrayTransforms ts) =+  flip (Foldable.foldl transformRows') ts+  where transformRows' inp (Rearrange cs perm) =+          addTransform (Rearrange cs (0:map (+1) perm)) inp+        transformRows' inp (Reshape cs shape) =+          addTransform (ReshapeInner cs shape) inp+        transformRows' inp (Replicate cs n)+          | inputRank inp == 1 =+            Rearrange mempty [1,0] `addTransform`+            (Replicate cs n `addTransform` inp)+          | otherwise =+            Rearrange mempty (2:0:1:[3..inputRank inp]) `addTransform`+            (Replicate cs n `addTransform`+             (Rearrange mempty (1:0:[2..inputRank inp-1]) `addTransform` inp))+        transformRows' inp nts =+          error $ "transformRows: Cannot transform this yet:\n" ++ show nts ++ "\n" ++ show inp++-- | Add to the input a 'Rearrange' transform that performs an @(k,n)@+-- transposition.  The new transform will be at the end of the current+-- transformation list.+transposeInput :: Int -> Int -> Input -> Input+transposeInput k n inp =+  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) [Input]+               | Scatter SubExp (Lambda lore) [Input] [(SubExp, Int, VName)]+               | Screma SubExp (ScremaForm lore) [Input]+               | Hist SubExp [HistOp lore] (Lambda lore) [Input]+            deriving (Eq, Show)++instance PP.Pretty Input where+  ppr (Input (ArrayTransforms ts) arr _) = foldl f (ppr arr) ts+    where f e (Rearrange cs perm) =+            text "rearrange" <> ppr cs <> PP.apply [PP.apply (map ppr perm), e]+          f e (Reshape cs shape) =+            text "reshape" <> ppr cs <> PP.apply [PP.apply (map ppr shape), e]+          f e (ReshapeOuter cs shape) =+            text "reshape_outer" <> ppr cs <> PP.apply [PP.apply (map ppr shape), e]+          f e (ReshapeInner cs shape) =+            text "reshape_inner" <> ppr cs <> PP.apply [PP.apply (map ppr shape), e]+          f e (Replicate cs ne) =+            text "replicate" <> ppr cs <> PP.apply [ppr ne, e]++instance PrettyLore lore => PP.Pretty (SOAC lore) where+  ppr (Screma w form arrs) = Futhark.ppScrema w form arrs+  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 (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 arrs (Stream w form lam _) =+  Stream (newWidth arrs w) form lam arrs+setInputs arrs (Scatter w lam _ivs as) =+  Scatter (newWidth arrs w) lam arrs as+setInputs arrs (Screma w form _) =+  Screma w form arrs+setInputs inps (Hist w ops lam _) =+  Hist w ops lam inps++newWidth :: [Input] -> SubExp -> SubExp+newWidth [] w = w+newWidth (inp:_) _ = arraySize 0 $ inputType inp++-- | The lambda used in a given SOAC.+lambda :: SOAC lore -> Lambda lore+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 lam (Stream w form _ arrs) =+  Stream w form lam arrs+setLambda lam (Scatter len _lam ivs as) =+  Scatter len lam ivs as+setLambda lam (Screma w (ScremaForm scan red _) arrs) =+  Screma w (ScremaForm scan red lam) arrs+setLambda lam (Hist w ops _ inps) =+  Hist w ops lam inps++-- | The return type of a SOAC.+typeOf :: SOAC lore -> [Type]+typeOf (Stream w form lam _) =+  let nes     = getStreamAccums form+      accrtps = take (length nes) $ lambdaReturnType lam+      arrtps  = [ arrayOf (stripArray 1 t) (Shape [w]) NoUniqueness+                  | t <- drop (length nes) (lambdaReturnType lam) ]+  in  accrtps ++ arrtps+typeOf (Scatter _w lam _ivs dests) =+  zipWith arrayOfRow (drop (n `div` 2) lam_ts) aws+  where lam_ts = lambdaReturnType lam+        n = length lam_ts+        (aws, _, _) = unzip3 dests+typeOf (Screma w form _) =+  scremaType w form+typeOf (Hist _ ops _ _) = do+  op <- ops+  map (`arrayOfRow` histWidth op) (lambdaReturnType $ histOp op)++-- | 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 (Stream w _ _ _) = w+width (Scatter len _lam _ivs _as) = len+width (Screma w _ _) = w+width (Hist w _ _ _) = w++-- | Convert a SOAC to the corresponding expression.+toExp :: (MonadBinder m, Op (Lore m) ~ Futhark.SOAC (Lore m)) =>+         SOAC (Lore m) -> m (Exp (Lore 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))+toSOAC (Stream w form lam inps) =+  Futhark.Stream w form lam <$> inputsToSubExps inps+toSOAC (Scatter len lam ivs dests) = do+  ivs' <- inputsToSubExps ivs+  return $ Futhark.Scatter len lam ivs' dests+toSOAC (Screma w form arrs) =+  Futhark.Screma w form <$> inputsToSubExps arrs+toSOAC (Hist w ops lam inps) =+  Futhark.Hist w ops lam <$> inputsToSubExps inps++-- | The reason why some expression cannot be converted to a 'SOAC'+-- value.+data NotSOAC = NotSOAC -- ^ The expression is not a (tuple-)SOAC at all.+               deriving (Show)++-- | Either convert an expression to the normalised SOAC+-- 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))+fromExp (Op (Futhark.Stream w form lam as)) =+  Right . Stream w form lam <$> traverse varInput as+fromExp (Op (Futhark.Scatter len lam ivs as)) =+  Right <$> (Scatter len lam <$> traverse varInput ivs <*> pure as)+fromExp (Op (Futhark.Screma w form arrs)) =+  Right . Screma w form <$> traverse varInput arrs+fromExp (Op (Futhark.Hist w ops lam arrs)) =+  Right . Hist w ops lam <$> traverse varInput arrs+fromExp _ = pure $ Left NotSOAC++-- | To-Stream translation of SOACs.+--   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])+soacToStream soac = do+  chunk_param <- newParam "chunk" $ Prim int32+  let chvar= Futhark.Var $ paramName chunk_param+      (lam, inps) = (lambda soac, inputs soac)+      w = width soac+  lam'     <- renameLambda lam+  let arrrtps= mapType w lam+      -- the chunked-outersize of the array result and input types+      loutps = [ arrayOfRow t chvar | t <- map rowType   arrrtps ]+      lintps = [ arrayOfRow t chvar | t <- map inputRowType inps ]++  strm_inpids <- mapM (newParam "inp") lintps+  -- Treat each SOAC case individually:+  case soac of+    Screma _ form _+      | Just _ <- Futhark.isMapSOAC form -> do+      -- Map(f,a) => is translated in strem's body to:+      -- let strm_resids = map(f,a_ch) in strm_resids+      --+      -- array result and input IDs of the stream's lambda+      strm_resids <- mapM (newIdent "res") loutps+      let insoac = Futhark.Screma chvar (Futhark.mapSOAC lam') $ map paramName strm_inpids+          insbnd = mkLet [] strm_resids $ Op insoac+          strmbdy= mkBody (oneStm insbnd) $ map (Futhark.Var . identName) strm_resids+          strmpar= chunk_param:strm_inpids+          strmlam= Lambda strmpar strmbdy loutps+          empty_lam = Lambda [] (mkBody mempty []) []+      -- map(f,a) creates a stream with NO accumulators+      return (Stream w (Parallel Disorder Commutative empty_lam []) strmlam inps, [])++      | Just (scans, _) <- Futhark.isScanomapSOAC form,+        Futhark.Scan scan_lam nes <- Futhark.singleScan scans -> do+      -- scanomap(scan_lam,nes,map_lam,a) => is translated in strem's body to:+      -- 1. let (scan0_ids,map_resids)   = scanomap(scan_lam, nes, map_lam, a_ch)+      -- 2. let strm_resids = map (acc `+`,nes, scan0_ids)+      -- 3. let outerszm1id = sizeof(0,strm_resids) - 1+      -- 4. let lasteel_ids = if outerszm1id < 0+      --                      then nes+      --                      else strm_resids[outerszm1id]+      -- 5. let acc'        = acc + lasteel_ids+      --    {acc', strm_resids, map_resids}+      -- the array and accumulator result types+      let scan_arr_ts = map (`arrayOfRow` chvar) $ lambdaReturnType scan_lam+          map_arr_ts = drop (length nes) loutps+          accrtps = lambdaReturnType scan_lam++      -- array result and input IDs of the stream's lambda+      strm_resids <- mapM (newIdent "res") scan_arr_ts+      scan0_ids <- mapM (newIdent "resarr0") scan_arr_ts+      map_resids <- mapM (newIdent "map_res") map_arr_ts++      lastel_ids <- mapM (newIdent "lstel") accrtps+      lastel_tmp_ids <- mapM (newIdent "lstel_tmp") accrtps+      empty_arr <- newIdent "empty_arr" $ Prim Bool+      inpacc_ids <- mapM (newParam "inpacc") accrtps+      outszm1id  <- newIdent "szm1" $ Prim int32+      -- 1. let (scan0_ids,map_resids)  = scanomap(scan_lam,nes,map_lam,a_ch)+      let insbnd = mkLet [] (scan0_ids++map_resids) $ Op $+                   Futhark.Screma chvar (Futhark.scanomapSOAC [Futhark.Scan scan_lam nes] lam') $+                   map paramName strm_inpids+      -- 2. let outerszm1id = chunksize - 1+          outszm1bnd = mkLet [] [outszm1id] $ BasicOp $+                       BinOp (Sub Int32 OverflowUndef)+                       (Futhark.Var $ paramName chunk_param)+                       (constant (1::Int32))+      -- 3. let lasteel_ids = ...+          empty_arr_bnd = mkLet [] [empty_arr] $ BasicOp $ CmpOp (CmpSlt Int32)+                          (Futhark.Var $ identName outszm1id)+                          (constant (0::Int32))+          leltmpbnds= zipWith (\ lid arrid -> mkLet [] [lid] $ BasicOp $+                                              Index (identName arrid) $+                                              fullSlice (identType arrid)+                                              [DimFix $ Futhark.Var $ identName outszm1id]+                              ) lastel_tmp_ids scan0_ids+          lelbnd = mkLet [] lastel_ids $+                   If (Futhark.Var $ identName empty_arr)+                   (mkBody mempty nes)+                   (mkBody (stmsFromList leltmpbnds) $+                    map (Futhark.Var . identName) lastel_tmp_ids) $+                   ifCommon $ map identType lastel_tmp_ids+      -- 4. let strm_resids = map (acc `+`,nes, scan0_ids)+      maplam <- mkMapPlusAccLam (map (Futhark.Var . paramName) inpacc_ids) scan_lam+      let mapbnd = mkLet [] strm_resids $ Op $+                   Futhark.Screma chvar (Futhark.mapSOAC maplam) $+                   map identName scan0_ids+      -- 5. let acc'        = acc + lasteel_ids+      addlelbdy <- mkPlusBnds scan_lam $ map Futhark.Var $+                   map paramName inpacc_ids++map identName lastel_ids+      -- Finally, construct the stream+      let (addlelbnd,addlelres) = (bodyStms addlelbdy, bodyResult addlelbdy)+          strmbdy= mkBody (stmsFromList [insbnd,outszm1bnd,empty_arr_bnd,lelbnd,mapbnd]<>addlelbnd) $+                          addlelres ++ map (Futhark.Var . identName) (strm_resids ++ map_resids)+          strmpar= chunk_param:inpacc_ids++strm_inpids+          strmlam= Lambda strmpar strmbdy (accrtps++loutps)+      return (Stream w (Sequential nes) strmlam inps,+              map paramIdent inpacc_ids)++      | Just (reds, _) <- Futhark.isRedomapSOAC form,+        Futhark.Reduce comm lamin nes <- Futhark.singleReduce reds -> do+      -- Redomap(+,lam,nes,a) => is translated in strem's body to:+      -- 1. let (acc0_ids,strm_resids) = redomap(+,lam,nes,a_ch) in+      -- 2. let acc'                   = acc + acc0_ids          in+      --    {acc', strm_resids}++      let accrtps= take (length nes) $ lambdaReturnType lam+          -- the chunked-outersize of the array result and input types+          loutps' = drop (length nes) loutps+          -- the lambda with proper index+          foldlam = lam'+      -- array result and input IDs of the stream's lambda+      strm_resids <- mapM (newIdent "res") loutps'+      inpacc_ids <- mapM (newParam "inpacc")  accrtps+      acc0_ids   <- mapM (newIdent "acc0"  )  accrtps+      -- 1. let (acc0_ids,strm_resids) = redomap(+,lam,nes,a_ch) in+      let insoac = Futhark.Screma chvar+                   (Futhark.redomapSOAC [Futhark.Reduce comm lamin nes] foldlam) $+                   map paramName strm_inpids+          insbnd = mkLet [] (acc0_ids++strm_resids) $ Op insoac+      -- 2. let acc'     = acc + acc0_ids    in+      addaccbdy <- mkPlusBnds lamin $ map Futhark.Var $+                   map paramName inpacc_ids++map identName acc0_ids+      -- Construct the stream+      let (addaccbnd,addaccres) = (bodyStms addaccbdy, bodyResult addaccbdy)+          strmbdy= mkBody (oneStm insbnd <> addaccbnd) $+                          addaccres ++ map (Futhark.Var . identName) strm_resids+          strmpar= chunk_param:inpacc_ids++strm_inpids+          strmlam= Lambda strmpar strmbdy (accrtps++loutps')+      lam0 <- renameLambda lamin+      return (Stream w (Parallel InOrder comm lam0 nes) strmlam inps, [])++    -- Otherwise it cannot become a stream.+    _ -> return (soac,[])+    where mkMapPlusAccLam :: (MonadFreshNames m, Bindable lore)+                          => [SubExp] -> Lambda lore -> m (Lambda lore)+          mkMapPlusAccLam accs plus = do+            let (accpars, rempars) = splitAt (length accs) $ lambdaParams plus+                parbnds = zipWith (\ par se -> mkLet [] [paramIdent par]+                                                        (BasicOp $ SubExp se)+                                  ) accpars accs+                plus_bdy = lambdaBody plus+                newlambdy = Body (bodyDec plus_bdy)+                                 (stmsFromList parbnds <> bodyStms plus_bdy)+                                 (bodyResult plus_bdy)+            renameLambda $ Lambda rempars newlambdy $ lambdaReturnType plus++          mkPlusBnds :: (MonadFreshNames m, Bindable lore)+                     => Lambda lore -> [SubExp] -> m (Body lore)+          mkPlusBnds plus accels = do+            plus' <- renameLambda plus+            let parbnds = zipWith (\ par se -> mkLet [] [paramIdent par]+                                                        (BasicOp $ SubExp se)+                                  ) (lambdaParams plus') accels+                body = lambdaBody plus'+            return $ body { bodyStms = stmsFromList parbnds <> bodyStms body }

@@ -1,155 +0,0 @@-{-# LANGUAGE FlexibleContexts #-}-{-# LANGUAGE TypeFamilies #-}-{-# LANGUAGE TupleSections #-}-module Futhark.Analysis.HORepresentation.MapNest-  ( Nesting (..)-  , MapNest (..)-  , typeOf-  , params-  , inputs-  , setInputs-  , fromSOAC-  , toSOAC-  )-where--import Data.List (find)-import Data.Maybe-import qualified Data.Map.Strict as M--import qualified Futhark.Analysis.HORepresentation.SOAC as SOAC-import Futhark.Analysis.HORepresentation.SOAC (SOAC)-import qualified Futhark.Representation.SOACS.SOAC as Futhark-import Futhark.Transform.Substitute-import Futhark.Representation.AST hiding (typeOf)-import Futhark.MonadFreshNames-import Futhark.Construct--data Nesting lore = Nesting {-    nestingParamNames   :: [VName]-  , nestingResult       :: [VName]-  , nestingReturnType   :: [Type]-  , nestingWidth        :: SubExp-  } deriving (Eq, Ord, Show)--data MapNest lore = MapNest SubExp (Lambda lore) [Nesting lore] [SOAC.Input]-                  deriving (Show)--typeOf :: MapNest lore -> [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 _ lam [] _)       =-  map paramName $ lambdaParams lam-params (MapNest _ _ (nest:_) _) =-  nestingParamNames nest--inputs :: MapNest lore -> [SOAC.Input]-inputs (MapNest _ _ _ inps) = inps--setInputs :: [SOAC.Input] -> MapNest lore -> MapNest lore-setInputs [] (MapNest w body ns _) = MapNest w body ns []-setInputs (inp:inps) (MapNest _ body ns _) = MapNest w body ns' (inp:inps)-  where w = arraySize 0 $ SOAC.inputType inp-        ws = drop 1 $ arrayDims $ SOAC.inputType inp-        ns' = zipWith setDepth ns ws-        setDepth n nw = n { nestingWidth = nw }--fromSOAC :: (Bindable lore, MonadFreshNames m,-             LocalScope lore m,-             Op lore ~ Futhark.SOAC lore) =>-            SOAC lore -> m (Maybe (MapNest lore))-fromSOAC = fromSOAC' mempty--fromSOAC' :: (Bindable lore, MonadFreshNames m,-              LocalScope lore m,-              Op lore ~ Futhark.SOAC lore) =>-             [Ident]-          -> SOAC lore-          -> m (Maybe (MapNest lore))--fromSOAC' bound (SOAC.Screma w (SOAC.ScremaForm [] [] lam) inps) = do-  maybenest <- case (stmsToList $ bodyStms $ lambdaBody lam,-                     bodyResult $ lambdaBody lam) of-    ([Let pat _ e], res) | res == map Var (patternNames pat) ->-      localScope (scopeOfLParams $ lambdaParams lam) $-      SOAC.fromExp e >>=-      either (return . Left) (fmap (Right . fmap (pat,)) . fromSOAC' bound')-    _ ->-      return $ Right Nothing--  case maybenest of-    -- Do we have a nested MapNest?-    Right (Just (pat, mn@(MapNest inner_w body' ns' inps'))) -> do-      (ps, inps'') <--        unzip <$>-        fixInputs w (zip (map paramName $ lambdaParams lam) inps)-        (zip (params mn) inps')-      let n' = Nesting { nestingParamNames = ps-                       , nestingResult     = patternNames pat-                       , nestingReturnType = typeOf mn-                       , nestingWidth      = inner_w-                       }-      return $ Just $ MapNest w body' (n':ns') inps''-    -- No nested MapNest it seems.-    _ -> do-      let isBound name-            | Just param <- find ((name==) . identName) bound =-              Just param-            | otherwise =-              Nothing-          boundUsedInBody =-            mapMaybe isBound $ namesToList $ freeIn lam-      newParams <- mapM (newIdent' (++"_wasfree")) boundUsedInBody-      let subst = M.fromList $-                  zip (map identName boundUsedInBody) (map identName newParams)-          inps' = inps ++-                  map (SOAC.addTransform (SOAC.Replicate mempty $ Shape [w]) . SOAC.identInput)-                  boundUsedInBody-          lam' =-            lam { lambdaBody =-                    substituteNames subst $ lambdaBody lam-                , lambdaParams =-                    lambdaParams lam ++ [ Param name t-                                        | Ident name t <- newParams ]-                }-      return $ Just $ MapNest w lam' [] inps'-  where bound' = bound <> map paramIdent (lambdaParams lam)--fromSOAC' _ _ = return Nothing--toSOAC :: (MonadFreshNames m, HasScope lore m,-           Bindable lore, BinderOps lore, Op lore ~ Futhark.SOAC lore) =>-          MapNest lore -> m (SOAC lore)-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-  let nparams = zipWith Param npnames $ map SOAC.inputRowType inps-  (e,bnds) <- runBinder $ localScope (scopeOfLParams nparams) $ SOAC.toExp =<<-    toSOAC (MapNest nw lam ns $ map (SOAC.identInput . paramIdent) nparams)-  bnd <- mkLetNames nres e-  let outerlam = Lambda { lambdaParams = nparams-                        , lambdaBody = mkBody (bnds<>oneStm bnd) $ map Var nres-                        , lambdaReturnType = nrettype-                        }-  return $ SOAC.Screma w (Futhark.mapSOAC outerlam) inps--fixInputs :: MonadFreshNames m =>-             SubExp -> [(VName, SOAC.Input)] -> [(VName, SOAC.Input)]-          -> m [(VName, SOAC.Input)]-fixInputs w ourInps = mapM inspect-  where-    isParam x (y, _) = x == y--    inspect (_, SOAC.Input ts v _)-      | Just (p,pInp) <- find (isParam v) ourInps = do-          let pInp' = SOAC.transformRows ts pInp-          p' <- newNameFromString $ baseString p-          return (p', pInp')--    inspect (param, SOAC.Input ts a t) = do-      param' <- newNameFromString (baseString param ++ "_rep")-      return (param', SOAC.Input (ts SOAC.|> SOAC.Replicate mempty (Shape [w])) a t)

@@ -1,637 +0,0 @@-{-# LANGUAGE TypeFamilies #-}-{-# LANGUAGE FlexibleInstances #-}--- | High-level representation of SOACs.  When performing--- SOAC-transformations, operating on normal 'Exp' values is somewhat--- of a nuisance, as they can represent terms that are not proper--- SOACs.  In contrast, this module exposes a SOAC representation that--- does not enable invalid representations (except for type errors).------ Furthermore, while standard normalised Futhark requires that the inputs--- to a SOAC are variables or constants, the representation in this--- module also supports various index-space transformations, like--- @replicate@ or @rearrange@.  This is also very convenient when--- implementing transformations.------ The names exported by this module conflict with the standard Futhark--- syntax tree constructors, so you are advised to use a qualified--- import:------ @--- import Futhark.Analysis.HORepresentation.SOAC (SOAC)--- import qualified Futhark.Analysis.HORepresentation.SOAC as SOAC--- @-module Futhark.Analysis.HORepresentation.SOAC-  (-   -- * SOACs-    SOAC (..)-  , Futhark.ScremaForm(..)-  , inputs-  , setInputs-  , lambda-  , setLambda-  , typeOf-  , width-  -- ** Converting to and from expressions-  , NotSOAC (..)-  , fromExp-  , toExp-  , toSOAC-  -- * SOAC inputs-  , Input (..)-  , varInput-  , identInput-  , isVarInput-  , isVarishInput-  , addTransform-  , addInitialTransforms-  , inputArray-  , inputRank-  , inputType-  , inputRowType-  , transformRows-  , transposeInput-  -- ** Input transformations-  , ArrayTransforms-  , noTransforms-  , nullTransforms-  , (|>)-  , (<|)-  , viewf-  , ViewF(..)-  , viewl-  , ViewL(..)-  , ArrayTransform(..)-  , transformFromExp-  , soacToStream-  )-  where--import Data.Foldable as Foldable-import Data.Maybe-import qualified Data.Sequence as Seq--import qualified Futhark.Representation.AST as Futhark-import Futhark.Representation.SOACS.SOAC-  (StreamForm(..), ScremaForm(..), scremaType, getStreamAccums, HistOp(..))-import qualified Futhark.Representation.SOACS.SOAC as Futhark-import Futhark.Representation.AST-  hiding (Var, Iota, Rearrange, Reshape, Replicate, typeOf)-import Futhark.Transform.Substitute-import Futhark.Construct hiding (toExp)-import Futhark.Transform.Rename (renameLambda)-import qualified Futhark.Util.Pretty as PP-import Futhark.Util.Pretty (ppr, text)---- | A single, simple transformation.  If you want several, don't just--- create a list, use 'ArrayTransforms' instead.-data ArrayTransform = Rearrange Certificates [Int]-                    -- ^ A permutation of an otherwise valid input.-                    | Reshape Certificates (ShapeChange SubExp)-                    -- ^ A reshaping of an otherwise valid input.-                    | ReshapeOuter Certificates (ShapeChange SubExp)-                    -- ^ A reshaping of the outer dimension.-                    | ReshapeInner Certificates (ShapeChange SubExp)-                    -- ^ A reshaping of everything but the outer dimension.-                    | Replicate Certificates Shape-                    -- ^ Replicate the rows of the array a number of times.-                      deriving (Show, Eq, Ord)--instance Substitute ArrayTransform where-  substituteNames substs (Rearrange cs xs) =-    Rearrange (substituteNames substs cs) xs-  substituteNames substs (Reshape cs ses) =-    Reshape (substituteNames substs cs) (substituteNames substs ses)-  substituteNames substs (ReshapeOuter cs ses) =-    ReshapeOuter (substituteNames substs cs) (substituteNames substs ses)-  substituteNames substs (ReshapeInner cs ses) =-    ReshapeInner (substituteNames substs cs) (substituteNames substs ses)-  substituteNames substs (Replicate cs se) =-    Replicate (substituteNames substs cs) (substituteNames substs se)---- | A sequence of array transformations, heavily inspired by--- "Data.Seq".  You can decompose it using 'viewF' and 'viewL', and--- grow it by using '|>' and '<|'.  These correspond closely to the--- similar operations for sequences, except that appending will try to--- normalise and simplify the transformation sequence.------ The data type is opaque in order to enforce normalisation--- invariants.  Basically, when you grow the sequence, the--- implementation will try to coalesce neighboring permutations, for--- example by composing permutations and removing identity--- transformations.-newtype ArrayTransforms = ArrayTransforms (Seq.Seq ArrayTransform)-  deriving (Eq, Ord, Show)--instance Semigroup ArrayTransforms where-  ts1 <> ts2 = case viewf ts2 of-                 t :< ts2' -> (ts1 |> t) <> ts2'-                 EmptyF    -> ts1--instance Monoid ArrayTransforms where-  mempty = noTransforms--instance Substitute ArrayTransforms where-  substituteNames substs (ArrayTransforms ts) =-    ArrayTransforms $ substituteNames substs <$> ts---- | The empty transformation list.-noTransforms :: ArrayTransforms-noTransforms = ArrayTransforms Seq.empty---- | Is it an empty transformation list?-nullTransforms :: ArrayTransforms -> Bool-nullTransforms (ArrayTransforms s) = Seq.null s---- | Decompose the input-end of the transformation sequence.-viewf :: ArrayTransforms -> ViewF-viewf (ArrayTransforms s) = case Seq.viewl s of-                              t Seq.:< s' -> t :< ArrayTransforms s'-                              Seq.EmptyL  -> EmptyF---- | A view of the first transformation to be applied.-data ViewF = EmptyF-           | ArrayTransform :< ArrayTransforms---- | Decompose the output-end of the transformation sequence.-viewl :: ArrayTransforms -> ViewL-viewl (ArrayTransforms s) = case Seq.viewr s of-                              s' Seq.:> t -> ArrayTransforms s' :> t-                              Seq.EmptyR  -> EmptyL---- | A view of the last transformation to be applied.-data ViewL = EmptyL-           | ArrayTransforms :> ArrayTransform---- | Add a transform to the end of the transformation list.-(|>) :: ArrayTransforms -> ArrayTransform -> ArrayTransforms-(|>) = flip $ addTransform' extract add $ uncurry (flip (,))-   where extract ts' = case viewl ts' of-                         EmptyL     -> Nothing-                         ts'' :> t' -> Just (t', ts'')-         add t' (ArrayTransforms ts') = ArrayTransforms $ ts' Seq.|> t'---- | Add a transform at the beginning of the transformation list.-(<|) :: ArrayTransform -> ArrayTransforms -> ArrayTransforms-(<|) = addTransform' extract add id-   where extract ts' = case viewf ts' of-                         EmptyF     -> Nothing-                         t' :< ts'' -> Just (t', ts'')-         add t' (ArrayTransforms ts') = ArrayTransforms $ t' Seq.<| ts'--addTransform' :: (ArrayTransforms -> Maybe (ArrayTransform, ArrayTransforms))-              -> (ArrayTransform -> ArrayTransforms -> ArrayTransforms)-              -> ((ArrayTransform,ArrayTransform) -> (ArrayTransform,ArrayTransform))-              -> ArrayTransform -> ArrayTransforms-              -> ArrayTransforms-addTransform' extract add swap t ts =-  fromMaybe (t `add` ts) $ do-    (t', ts') <- extract ts-    combined <- uncurry combineTransforms $ swap (t', t)-    Just $ if identityTransform combined then ts'-           else addTransform' extract add swap combined ts'--identityTransform :: ArrayTransform -> Bool-identityTransform (Rearrange _ perm) =-  Foldable.and $ zipWith (==) perm [0..]-identityTransform _ = False--combineTransforms :: ArrayTransform -> ArrayTransform -> Maybe ArrayTransform-combineTransforms (Rearrange cs2 perm2) (Rearrange cs1 perm1) =-  Just $ Rearrange (cs1<>cs2) $ perm2 `rearrangeCompose` perm1-combineTransforms _ _ = Nothing---- | Given an expression, determine whether the expression represents--- 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 cs (BasicOp (Futhark.Rearrange perm v)) =-  Just (v, Rearrange cs perm)-transformFromExp cs (BasicOp (Futhark.Reshape shape v)) =-  Just (v, Reshape cs shape)-transformFromExp cs (BasicOp (Futhark.Replicate shape (Futhark.Var v))) =-  Just (v, Replicate cs shape)-transformFromExp _ _ = Nothing---- | One array input to a SOAC - a SOAC may have multiple inputs, but--- all are of this form.  Only the array inputs are expressed with--- this type; other arguments, such as initial accumulator values, are--- plain expressions.  The transforms are done left-to-right, that is,--- the first element of the 'ArrayTransform' list is applied first.-data Input = Input ArrayTransforms VName Type-             deriving (Show, Eq, Ord)--instance Substitute Input where-  substituteNames substs (Input ts v t) =-    Input (substituteNames substs ts)-    (substituteNames substs v) (substituteNames substs t)---- | Create a plain array variable input with no transformations.-varInput :: HasScope t f => VName -> f Input-varInput v = withType <$> lookupType v-  where withType = Input (ArrayTransforms Seq.empty) v---- | Create a plain array variable input with no transformations, from an 'Ident'.-identInput :: Ident -> Input-identInput v = Input (ArrayTransforms Seq.empty) (identName v) (identType v)---- | If the given input is a plain variable input, with no transforms,--- return the variable.-isVarInput :: Input -> Maybe VName-isVarInput (Input ts v _) | nullTransforms ts = Just v-isVarInput _                                  = Nothing---- | If the given input is a plain variable input, with no non-vacuous transforms,--- return the variable.-isVarishInput :: Input -> Maybe VName-isVarishInput (Input ts v t)-  | nullTransforms ts = Just v-  | Reshape cs [DimCoercion _] :< ts' <- viewf ts, cs == mempty =-      isVarishInput $ Input ts' v t-isVarishInput _ = Nothing---- | Add a transformation to the end of the transformation list.-addTransform :: ArrayTransform -> Input -> Input-addTransform tr (Input trs a t) =-  Input (trs |> tr) a t---- | Add several transformations to the start of the transformation--- list.-addInitialTransforms :: ArrayTransforms -> Input -> Input-addInitialTransforms ts (Input ots a t) = Input (ts <> ots) a t---- | Convert SOAC inputs to the corresponding expressions.-inputsToSubExps :: (MonadBinder m) =>-                   [Input] -> m [VName]-inputsToSubExps = mapM inputToExp'-  where inputToExp' (Input (ArrayTransforms ts) a _) =-          foldlM transform a ts--        transform ia (Replicate cs n) =-          certifying cs $-          letExp "repeat" $ BasicOp $ Futhark.Replicate n (Futhark.Var ia)--        transform ia (Rearrange cs perm) =-          certifying cs $-          letExp "rearrange" $ BasicOp $ Futhark.Rearrange perm ia--        transform ia (Reshape cs shape) =-          certifying cs $-          letExp "reshape" $ BasicOp $ Futhark.Reshape shape ia--        transform ia (ReshapeOuter cs shape) = do-          shape' <- reshapeOuter shape 1 . arrayShape <$> lookupType ia-          certifying cs $-            letExp "reshape_outer" $ BasicOp $ Futhark.Reshape shape' ia--        transform ia (ReshapeInner cs shape) = do-          shape' <- reshapeInner shape 1 . arrayShape <$> lookupType ia-          certifying cs $-            letExp "reshape_inner" $ BasicOp $ Futhark.Reshape shape' ia---- | Return the array name of the input.-inputArray :: Input -> VName-inputArray (Input _ v _) = v---- | Return the type of an input.-inputType :: Input -> Type-inputType (Input (ArrayTransforms ts) _ at) =-  Foldable.foldl transformType at ts-  where transformType t (Replicate _ shape) =-          arrayOfShape t shape-        transformType t (Rearrange _ perm) =-          rearrangeType perm t-        transformType t (Reshape _ shape) =-          t `setArrayShape` newShape shape-        transformType t (ReshapeOuter _ shape) =-          let Shape oldshape = arrayShape t-          in t `setArrayShape` Shape (newDims shape ++ drop 1 oldshape)-        transformType t (ReshapeInner _ shape) =-          let Shape oldshape = arrayShape t-          in t `setArrayShape` Shape (take 1 oldshape ++ newDims shape)---- | Return the row type of an input.  Just a convenient alias.-inputRowType :: Input -> Type-inputRowType = rowType . inputType---- | Return the array rank (dimensionality) of an input.  Just a--- convenient alias.-inputRank :: Input -> Int-inputRank = arrayRank . inputType---- | Apply the transformations to every row of the input.-transformRows :: ArrayTransforms -> Input -> Input-transformRows (ArrayTransforms ts) =-  flip (Foldable.foldl transformRows') ts-  where transformRows' inp (Rearrange cs perm) =-          addTransform (Rearrange cs (0:map (+1) perm)) inp-        transformRows' inp (Reshape cs shape) =-          addTransform (ReshapeInner cs shape) inp-        transformRows' inp (Replicate cs n)-          | inputRank inp == 1 =-            Rearrange mempty [1,0] `addTransform`-            (Replicate cs n `addTransform` inp)-          | otherwise =-            Rearrange mempty (2:0:1:[3..inputRank inp]) `addTransform`-            (Replicate cs n `addTransform`-             (Rearrange mempty (1:0:[2..inputRank inp-1]) `addTransform` inp))-        transformRows' inp nts =-          error $ "transformRows: Cannot transform this yet:\n" ++ show nts ++ "\n" ++ show inp---- | Add to the input a 'Rearrange' transform that performs an @(k,n)@--- transposition.  The new transform will be at the end of the current--- transformation list.-transposeInput :: Int -> Int -> Input -> Input-transposeInput k n inp =-  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) [Input]-               | Scatter SubExp (Lambda lore) [Input] [(SubExp, Int, VName)]-               | Screma SubExp (ScremaForm lore) [Input]-               | Hist SubExp [HistOp lore] (Lambda lore) [Input]-            deriving (Eq, Show)--instance PP.Pretty Input where-  ppr (Input (ArrayTransforms ts) arr _) = foldl f (ppr arr) ts-    where f e (Rearrange cs perm) =-            text "rearrange" <> ppr cs <> PP.apply [PP.apply (map ppr perm), e]-          f e (Reshape cs shape) =-            text "reshape" <> ppr cs <> PP.apply [PP.apply (map ppr shape), e]-          f e (ReshapeOuter cs shape) =-            text "reshape_outer" <> ppr cs <> PP.apply [PP.apply (map ppr shape), e]-          f e (ReshapeInner cs shape) =-            text "reshape_inner" <> ppr cs <> PP.apply [PP.apply (map ppr shape), e]-          f e (Replicate cs ne) =-            text "replicate" <> ppr cs <> PP.apply [ppr ne, e]--instance PrettyLore lore => PP.Pretty (SOAC lore) where-  ppr (Screma w form arrs) = Futhark.ppScrema w form arrs-  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 (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 arrs (Stream w form lam _) =-  Stream (newWidth arrs w) form lam arrs-setInputs arrs (Scatter w lam _ivs as) =-  Scatter (newWidth arrs w) lam arrs as-setInputs arrs (Screma w form _) =-  Screma w form arrs-setInputs inps (Hist w ops lam _) =-  Hist w ops lam inps--newWidth :: [Input] -> SubExp -> SubExp-newWidth [] w = w-newWidth (inp:_) _ = arraySize 0 $ inputType inp---- | The lambda used in a given SOAC.-lambda :: SOAC lore -> Lambda lore-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 lam (Stream w form _ arrs) =-  Stream w form lam arrs-setLambda lam (Scatter len _lam ivs as) =-  Scatter len lam ivs as-setLambda lam (Screma w (ScremaForm scan red _) arrs) =-  Screma w (ScremaForm scan red lam) arrs-setLambda lam (Hist w ops _ inps) =-  Hist w ops lam inps---- | The return type of a SOAC.-typeOf :: SOAC lore -> [Type]-typeOf (Stream w form lam _) =-  let nes     = getStreamAccums form-      accrtps = take (length nes) $ lambdaReturnType lam-      arrtps  = [ arrayOf (stripArray 1 t) (Shape [w]) NoUniqueness-                  | t <- drop (length nes) (lambdaReturnType lam) ]-  in  accrtps ++ arrtps-typeOf (Scatter _w lam _ivs dests) =-  zipWith arrayOfRow (drop (n `div` 2) lam_ts) aws-  where lam_ts = lambdaReturnType lam-        n = length lam_ts-        (aws, _, _) = unzip3 dests-typeOf (Screma w form _) =-  scremaType w form-typeOf (Hist _ ops _ _) = do-  op <- ops-  map (`arrayOfRow` histWidth op) (lambdaReturnType $ histOp op)---- | 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 (Stream w _ _ _) = w-width (Scatter len _lam _ivs _as) = len-width (Screma w _ _) = w-width (Hist w _ _ _) = w---- | Convert a SOAC to the corresponding expression.-toExp :: (MonadBinder m, Op (Lore m) ~ Futhark.SOAC (Lore m)) =>-         SOAC (Lore m) -> m (Exp (Lore 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))-toSOAC (Stream w form lam inps) =-  Futhark.Stream w form lam <$> inputsToSubExps inps-toSOAC (Scatter len lam ivs dests) = do-  ivs' <- inputsToSubExps ivs-  return $ Futhark.Scatter len lam ivs' dests-toSOAC (Screma w form arrs) =-  Futhark.Screma w form <$> inputsToSubExps arrs-toSOAC (Hist w ops lam inps) =-  Futhark.Hist w ops lam <$> inputsToSubExps inps---- | The reason why some expression cannot be converted to a 'SOAC'--- value.-data NotSOAC = NotSOAC -- ^ The expression is not a (tuple-)SOAC at all.-               deriving (Show)---- | Either convert an expression to the normalised SOAC--- 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))-fromExp (Op (Futhark.Stream w form lam as)) =-  Right . Stream w form lam <$> traverse varInput as-fromExp (Op (Futhark.Scatter len lam ivs as)) =-  Right <$> (Scatter len lam <$> traverse varInput ivs <*> pure as)-fromExp (Op (Futhark.Screma w form arrs)) =-  Right . Screma w form <$> traverse varInput arrs-fromExp (Op (Futhark.Hist w ops lam arrs)) =-  Right . Hist w ops lam <$> traverse varInput arrs-fromExp _ = pure $ Left NotSOAC---- | To-Stream translation of SOACs.---   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])-soacToStream soac = do-  chunk_param <- newParam "chunk" $ Prim int32-  let chvar= Futhark.Var $ paramName chunk_param-      (lam, inps) = (lambda soac, inputs soac)-      w = width soac-  lam'     <- renameLambda lam-  let arrrtps= mapType w lam-      -- the chunked-outersize of the array result and input types-      loutps = [ arrayOfRow t chvar | t <- map rowType   arrrtps ]-      lintps = [ arrayOfRow t chvar | t <- map inputRowType inps ]--  strm_inpids <- mapM (newParam "inp") lintps-  -- Treat each SOAC case individually:-  case soac of-    Screma _ form _-      | Just _ <- Futhark.isMapSOAC form -> do-      -- Map(f,a) => is translated in strem's body to:-      -- let strm_resids = map(f,a_ch) in strm_resids-      ---      -- array result and input IDs of the stream's lambda-      strm_resids <- mapM (newIdent "res") loutps-      let insoac = Futhark.Screma chvar (Futhark.mapSOAC lam') $ map paramName strm_inpids-          insbnd = mkLet [] strm_resids $ Op insoac-          strmbdy= mkBody (oneStm insbnd) $ map (Futhark.Var . identName) strm_resids-          strmpar= chunk_param:strm_inpids-          strmlam= Lambda strmpar strmbdy loutps-          empty_lam = Lambda [] (mkBody mempty []) []-      -- map(f,a) creates a stream with NO accumulators-      return (Stream w (Parallel Disorder Commutative empty_lam []) strmlam inps, [])--      | Just (scans, _) <- Futhark.isScanomapSOAC form,-        Futhark.Scan scan_lam nes <- Futhark.singleScan scans -> do-      -- scanomap(scan_lam,nes,map_lam,a) => is translated in strem's body to:-      -- 1. let (scan0_ids,map_resids)   = scanomap(scan_lam, nes, map_lam, a_ch)-      -- 2. let strm_resids = map (acc `+`,nes, scan0_ids)-      -- 3. let outerszm1id = sizeof(0,strm_resids) - 1-      -- 4. let lasteel_ids = if outerszm1id < 0-      --                      then nes-      --                      else strm_resids[outerszm1id]-      -- 5. let acc'        = acc + lasteel_ids-      --    {acc', strm_resids, map_resids}-      -- the array and accumulator result types-      let scan_arr_ts = map (`arrayOfRow` chvar) $ lambdaReturnType scan_lam-          map_arr_ts = drop (length nes) loutps-          accrtps = lambdaReturnType scan_lam--      -- array result and input IDs of the stream's lambda-      strm_resids <- mapM (newIdent "res") scan_arr_ts-      scan0_ids <- mapM (newIdent "resarr0") scan_arr_ts-      map_resids <- mapM (newIdent "map_res") map_arr_ts--      lastel_ids <- mapM (newIdent "lstel") accrtps-      lastel_tmp_ids <- mapM (newIdent "lstel_tmp") accrtps-      empty_arr <- newIdent "empty_arr" $ Prim Bool-      inpacc_ids <- mapM (newParam "inpacc") accrtps-      outszm1id  <- newIdent "szm1" $ Prim int32-      -- 1. let (scan0_ids,map_resids)  = scanomap(scan_lam,nes,map_lam,a_ch)-      let insbnd = mkLet [] (scan0_ids++map_resids) $ Op $-                   Futhark.Screma chvar (Futhark.scanomapSOAC [Futhark.Scan scan_lam nes] lam') $-                   map paramName strm_inpids-      -- 2. let outerszm1id = chunksize - 1-          outszm1bnd = mkLet [] [outszm1id] $ BasicOp $-                       BinOp (Sub Int32 OverflowUndef)-                       (Futhark.Var $ paramName chunk_param)-                       (constant (1::Int32))-      -- 3. let lasteel_ids = ...-          empty_arr_bnd = mkLet [] [empty_arr] $ BasicOp $ CmpOp (CmpSlt Int32)-                          (Futhark.Var $ identName outszm1id)-                          (constant (0::Int32))-          leltmpbnds= zipWith (\ lid arrid -> mkLet [] [lid] $ BasicOp $-                                              Index (identName arrid) $-                                              fullSlice (identType arrid)-                                              [DimFix $ Futhark.Var $ identName outszm1id]-                              ) lastel_tmp_ids scan0_ids-          lelbnd = mkLet [] lastel_ids $-                   If (Futhark.Var $ identName empty_arr)-                   (mkBody mempty nes)-                   (mkBody (stmsFromList leltmpbnds) $-                    map (Futhark.Var . identName) lastel_tmp_ids) $-                   ifCommon $ map identType lastel_tmp_ids-      -- 4. let strm_resids = map (acc `+`,nes, scan0_ids)-      maplam <- mkMapPlusAccLam (map (Futhark.Var . paramName) inpacc_ids) scan_lam-      let mapbnd = mkLet [] strm_resids $ Op $-                   Futhark.Screma chvar (Futhark.mapSOAC maplam) $-                   map identName scan0_ids-      -- 5. let acc'        = acc + lasteel_ids-      addlelbdy <- mkPlusBnds scan_lam $ map Futhark.Var $-                   map paramName inpacc_ids++map identName lastel_ids-      -- Finally, construct the stream-      let (addlelbnd,addlelres) = (bodyStms addlelbdy, bodyResult addlelbdy)-          strmbdy= mkBody (stmsFromList [insbnd,outszm1bnd,empty_arr_bnd,lelbnd,mapbnd]<>addlelbnd) $-                          addlelres ++ map (Futhark.Var . identName) (strm_resids ++ map_resids)-          strmpar= chunk_param:inpacc_ids++strm_inpids-          strmlam= Lambda strmpar strmbdy (accrtps++loutps)-      return (Stream w (Sequential nes) strmlam inps,-              map paramIdent inpacc_ids)--      | Just (reds, _) <- Futhark.isRedomapSOAC form,-        Futhark.Reduce comm lamin nes <- Futhark.singleReduce reds -> do-      -- Redomap(+,lam,nes,a) => is translated in strem's body to:-      -- 1. let (acc0_ids,strm_resids) = redomap(+,lam,nes,a_ch) in-      -- 2. let acc'                   = acc + acc0_ids          in-      --    {acc', strm_resids}--      let accrtps= take (length nes) $ lambdaReturnType lam-          -- the chunked-outersize of the array result and input types-          loutps' = drop (length nes) loutps-          -- the lambda with proper index-          foldlam = lam'-      -- array result and input IDs of the stream's lambda-      strm_resids <- mapM (newIdent "res") loutps'-      inpacc_ids <- mapM (newParam "inpacc")  accrtps-      acc0_ids   <- mapM (newIdent "acc0"  )  accrtps-      -- 1. let (acc0_ids,strm_resids) = redomap(+,lam,nes,a_ch) in-      let insoac = Futhark.Screma chvar-                   (Futhark.redomapSOAC [Futhark.Reduce comm lamin nes] foldlam) $-                   map paramName strm_inpids-          insbnd = mkLet [] (acc0_ids++strm_resids) $ Op insoac-      -- 2. let acc'     = acc + acc0_ids    in-      addaccbdy <- mkPlusBnds lamin $ map Futhark.Var $-                   map paramName inpacc_ids++map identName acc0_ids-      -- Construct the stream-      let (addaccbnd,addaccres) = (bodyStms addaccbdy, bodyResult addaccbdy)-          strmbdy= mkBody (oneStm insbnd <> addaccbnd) $-                          addaccres ++ map (Futhark.Var . identName) strm_resids-          strmpar= chunk_param:inpacc_ids++strm_inpids-          strmlam= Lambda strmpar strmbdy (accrtps++loutps')-      lam0 <- renameLambda lamin-      return (Stream w (Parallel InOrder comm lam0 nes) strmlam inps, [])--    -- Otherwise it cannot become a stream.-    _ -> return (soac,[])-    where mkMapPlusAccLam :: (MonadFreshNames m, Bindable lore)-                          => [SubExp] -> Lambda lore -> m (Lambda lore)-          mkMapPlusAccLam accs plus = do-            let (accpars, rempars) = splitAt (length accs) $ lambdaParams plus-                parbnds = zipWith (\ par se -> mkLet [] [paramIdent par]-                                                        (BasicOp $ SubExp se)-                                  ) accpars accs-                plus_bdy = lambdaBody plus-                newlambdy = Body (bodyAttr plus_bdy)-                                 (stmsFromList parbnds <> bodyStms plus_bdy)-                                 (bodyResult plus_bdy)-            renameLambda $ Lambda rempars newlambdy $ lambdaReturnType plus--          mkPlusBnds :: (MonadFreshNames m, Bindable lore)-                     => Lambda lore -> [SubExp] -> m (Body lore)-          mkPlusBnds plus accels = do-            plus' <- renameLambda plus-            let parbnds = zipWith (\ par se -> mkLet [] [paramIdent par]-                                                        (BasicOp $ SubExp se)-                                  ) (lambdaParams plus') accels-                body = lambdaBody plus'-            return $ body { bodyStms = stmsFromList parbnds <> bodyStms body }