futhark 0.25.3 → 0.25.4

raw patch · 23 files changed

+266/−187 lines, 23 filesdep ~lspPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: lsp

API changes (from Hackage documentation)

Files

• docs/error-index.rst +6/−5
• docs/glossary.rst +12/−0
• docs/language-reference.rst +86/−62
• futhark.cabal +1/−1
• src/Futhark/AD/Rev/Reduce.hs +1/−1
• src/Futhark/AD/Rev/Scan.hs +7/−8
• src/Futhark/Analysis/SymbolTable.hs +10/−9
• src/Futhark/Analysis/UsageTable.hs +1/−5
• src/Futhark/CodeGen/Backends/GenericC.hs +1/−1
• src/Futhark/CodeGen/ImpGen/GPU/SegScan/SinglePass.hs +2/−2
• src/Futhark/Construct.hs +8/−6
• src/Futhark/IR/Mem.hs +1/−1
• src/Futhark/IR/Mem/IxFun.hs +1/−1
• src/Futhark/IR/Mem/LMAD.hs +26/−18
• src/Futhark/IR/SOACS/Simplify.hs +18/−3
• src/Futhark/IR/SegOp.hs +7/−15
• src/Futhark/Internalise/Monomorphise.hs +2/−1
• src/Futhark/Optimise/TileLoops.hs +2/−1
• src/Futhark/Optimise/Unstream.hs +6/−10
• src/Futhark/Pass/ExtractKernels/DistributeNests.hs +38/−27
• src/Language/Futhark/Prop.hs +11/−5
• src/Language/Futhark/TypeChecker/Terms.hs +10/−5
• unittests/Futhark/IR/Mem/IxFunTests.hs +9/−0

@@ -484,11 +484,12 @@ Whenever ``length`` occurs (as in the composition above), the type checker must *instantiate* the ``[n]`` with the concrete symbolic size of its input array.  But in the composition, that size does not-actually exist until ``filter`` has been run.  For that matter, the-type checker does not know what ``>->`` does, and for all it knows it-may actually apply ``filter`` many times to different arrays, yielding-different sizes.  This makes it impossible to uniquely instantiate the-type of ``length``, and therefore the program is rejected.+actually exist until ``filter`` has been fully applied.  For that+matter, the type checker does not know what ``>->`` does, and for all+it knows it may actually apply ``filter`` many times to different+arrays, yielding different sizes.  This makes it impossible to+uniquely instantiate the type of ``length``, and therefore the program+is rejected.  The common workaround is to use *pipelining* instead of composition whenever we use functions with existential return types:

@@ -269,6 +269,12 @@      :term:`polymorphic` functions for each type it is used with.      Performed by the Futhark compiler. +   Name++     A lexical token consisting of alphanumeric characters and+     underscores, for example ``map`` and ``do_it``.  Most variables+     are names.  See also :term:`symbol`.+    Nested data parallelism       Nested :term:`data parallelism` occurs when a parallel construct@@ -346,6 +352,12 @@      Futhark: functions such as ``map``, ``reduce``, ``scan``, and so      on.  They are *second order* because they accept a functional      argument, and so permit :term:`nested data parallelism`.++   Symbol++     A lexical token that consts of symbolic (non-alphabetic+     characters), and can be bound to a value.  Infix operators such+     as ``+`` and ``/`` are symbols.  See also :term:`name`.     Type 

@@ -30,26 +30,46 @@ ------------------------  .. productionlist::-   id: `letter` `constituent`* | "_" `constituent`*+   name: `letter` `constituent`* | "_" `constituent`*    constituent: `letter` | `digit` | "_" | "'"-   quals: (`id` ".")+-   qualid: `id` | `quals` `id`-   binop: `opstartchar` `opchar`*-   qualbinop: `binop` | `quals` `binop` | "`" `qualid` "`"-   fieldid: `decimal` | `id`-   opstartchar: "+" | "-" | "*" | "/" | "%" | "=" | "!" | ">" | "<" | "|" | "&" | "^"-   opchar: `opstartchar` | "."-   constructor: "#" `id`+   quals: (`name` ".")++   qualname: `name` | `quals` `name`+   symbol: `symstartchar` `symchar`*+   qualsymbol: `symbol` | `quals` `symbol` | "`" `qualname` "`"+   fieldid: `decimal` | `name`+   symstartchar: "+" | "-" | "*" | "/" | "%" | "=" | "!" | ">" | "<" | "|" | "&" | "^"+   symchar: `symstartchar` | "."+   constructor: "#" `name`  Many things in Futhark are named. When we are defining something, we-give it an unqualified name (`id`).  When referencing something inside-a module, we use a qualified name (`qualid`).  The constructor names-of a sum type are identifiers prefixed with ``#``, with no space-afterwards.  The fields of a record are named with `fieldid`.  Note-that a `fieldid` can be a decimal number.  Futhark has three distinct-name spaces: terms, module types, and types.  Modules (including-parametric modules) and values both share the term namespace.+give it an unqualified name (`name`).  When referencing something+inside a module, we use a qualified name (`qualname`).  We can also+use symbols (`symbol`, `qualsymbol`), which are treated as infix by+the grammar. +The constructor names of a sum type are identifiers prefixed with+``#``, with no space afterwards.  The fields of a record are named+with `fieldid`.  Note that a `fieldid` can be a decimal number.+Futhark has three distinct name spaces: terms, module types, and+types.  Modules (including parametric modules) and values both share+the term namespace.++.. _reserved:++Reserved names and symbols+~~~~~~~~~~~~~~~~~~~~~~~~~~++A reserved name or symbol may be used only when explicitly present in+the grammar.  In particular, they cannot be bound in definitions.++The following identifier are reserved: ``true``, ``false``, ``if``,+``then``, ``else``, ``def``, ``let``, ``loop``, ``in``, ``val``,+``for``, ``do``, ``with``, ``local``, ``open``, ``include``,+``import``, ``type``, ``entry``, ``module``, ``while``, ``assert``,+``match``, ``case``.++The following symbols are reserved: ``=``.+ .. _primitives:  Primitive Types and Values@@ -106,7 +126,7 @@ ~~~~~~~~~~~~~~~~~~~~~~~~~  .. productionlist::-   type:   `qualid`+   type:   `qualname`        : | `array_type`        : | `tuple_type`        : | `record_type`@@ -197,7 +217,7 @@  .. productionlist::    function_type: `param_type` "->" `type`-   param_type: `type` | "(" `id` ":" `type` ")"+   param_type: `type` | "(" `name` ":" `type` ")"  Functions are classified via function types, but they are not fully first class.  See :ref:`hofs` for the details.@@ -214,7 +234,7 @@ corresponding Unicode code point.  .. productionlist::-   existential_size: "?" ("[" `id` "]")+ "." `type`+   existential_size: "?" ("[" `name` "]")+ "." `type`  An existential size quantifier brings an unknown size into scope within a type.  This can be used to encode constraints for statically@@ -253,8 +273,8 @@ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  .. productionlist::-   val_bind:   ("def" | "entry" | "let") (`id` | "(" `binop` ")") `type_param`* `pat`* [":" `type`] "=" `exp`-           : | ("def" | "entry" | "let") `pat` `binop` `pat` [":" `type`] "=" `exp`+   val_bind:   ("def" | "entry" | "let") (`name` | "(" `symbol` ")") `type_param`* `pat`* [":" `type`] "=" `exp`+           : | ("def" | "entry" | "let") `pat` `symbol` `pat` [":" `type`] "=" `exp`  **Note:** using ``let`` to define top-level bindings is deprecated. @@ -375,8 +395,8 @@ ~~~~~~~~~~~~~~~~~~  .. productionlist::-   type_bind: ("type" | "type^" | "type~") `id` `type_param`* "=" `type`-   type_param: "[" `id` "]" | "'" `id` | "'~" `id` | "'^" `id`+   type_bind: ("type" | "type^" | "type~") `name` `type_param`* "=" `type`+   type_param: "[" `name` "]" | "'" `name` | "'~" `name` | "'^" `name`  Type abbreviations function as shorthands for the purpose of documentation or brevity.  After a type binding ``type t1 = t2``, the@@ -433,7 +453,7 @@  .. productionlist::    atom:   `literal`-       : | `qualid` ("." `fieldid`)*+       : | `qualname` ("." `fieldid`)*        : | `stringlit`        : | `charlit`        : | "(" ")"@@ -441,18 +461,18 @@        : | "(" `exp` ("," `exp`)* ")"        : | "{" "}"        : | "{" `field` ("," `field`)* "}"-       : | `qualid` "[" `index` ("," `index`)* "]"+       : | `qualname` "[" `index` ("," `index`)* "]"        : | "(" `exp` ")" "[" `index` ("," `index`)* "]"        : | `quals` "." "(" `exp` ")"        : | "[" `exp` ("," `exp`)* "]"-       : | "(" `qualbinop` ")"-       : | "(" `exp` `qualbinop` ")"-       : | "(" `qualbinop` `exp` ")"+       : | "(" `qualsymbol` ")"+       : | "(" `exp` `qualsymbol` ")"+       : | "(" `qualsymbol` `exp` ")"        : | "(" ( "." `field` )+ ")"        : | "(" "." "[" `index` ("," `index`)* "]" ")"        : | "???"    exp:   `atom`-      : | `exp` `qualbinop` `exp`+      : | `exp` `qualsymbol` `exp`       : | `exp` `exp`       : | "!" `exp`       : | "-" `exp`@@ -464,8 +484,8 @@       : | `exp` [ ".." `exp` ] "..>" `exp`       : | "if" `exp` "then" `exp` "else" `exp`       : | "let" `size`* `pat` "=" `exp` "in" `exp`-      : | "let" `id` "[" `index` ("," `index`)* "]" "=" `exp` "in" `exp`-      : | "let" `id` `type_param`* `pat`+ [":" `type`] "=" `exp` "in" `exp`+      : | "let" `name` "[" `index` ("," `index`)* "]" "=" `exp` "in" `exp`+      : | "let" `name` `type_param`* `pat`+ [":" `type`] "=" `exp` "in" `exp`       : | "(" "\" `pat`+ [":" `type`] "->" `exp` ")"       : | "loop" `pat` ["=" `exp`] `loopform` "do" `exp`       : | "#[" `attr` "]" `exp`@@ -475,9 +495,9 @@       : | `exp` "with" `fieldid` ("." `fieldid`)* "=" `exp`       : | "match" `exp` ("case" `pat` "->" `exp`)+    field:   `fieldid` "=" `exp`-        : | `id`-   size : "[" `id` "]"-   pat:   `id`+        : | `name`+   size : "[" `name` "]"+   pat:   `name`       : | `pat_literal`       : | "_"       : | "(" ")"@@ -493,7 +513,7 @@               : | `charlit`               : | "true"               : | "false"-   loopform :   "for" `id` "<" `exp`+   loopform :   "for" `name` "<" `exp`             : | "for" `pat` "in" `exp`             : | "while" `exp`    index:   `exp` [":" [`exp`]] [":" [`exp`]]@@ -523,7 +543,7 @@ * A type ascription (``exp : type``) cannot appear as an array   index, as it conflicts with the syntax for slicing. -* In ``f [x]``, there is am ambiguity between indexing the array ``f``+* In ``f [x]``, there is an ambiguity between indexing the array ``f``   at position ``x``, or calling the function ``f`` with the singleton   array ``x``.  We resolve this the following way: @@ -536,17 +556,21 @@   enclosed in parentheses, rather than an operator section partially   applying the infix operator ``-``. -* Function and type application, and prefix operators, bind more-  tightly than any infix operator.  Note that the only prefix-  operators are the builtin ``!`` and ``-``, and more cannot be-  defined.  In particular, a user-defined operator beginning with-  ``!`` binds as ``!=``, as on the table below, not as the prefix+* Prefix operators bind more tighly than infix operators.  Note that+  the only prefix operators are the builtin ``!`` and ``-``, and more+  cannot be defined.  In particular, a user-defined operator beginning+  with ``!`` binds as ``!=``, as on the table below, not as the prefix   operator ``!`` +* Function and type application binds more tightly than infix+  operators.+ * ``#foo #bar`` is interpreted as a constructor with a ``#bar``   payload, not as applying ``#foo`` to ``#bar`` (the latter would be   semantically invalid anyway). +* `Attributes`_ bind less tightly than any other syntactic construct.+ * A type application ``pt [n]t`` is parsed as an application of the   type constructor ``pt`` to the size argument ``[n]`` and the type   ``t``.  To pass a single array-typed parameter, enclose it in@@ -564,7 +588,7 @@   =================  =============   left               ``,``   left               ``:``, ``:>``-  left               ```op```+  left               ```symbol```   left               ``||``   left               ``&&``   left               ``<=`` ``>=`` ``>`` ``<`` ``==`` ``!=`` ``!`` ``=``@@ -603,8 +627,8 @@  Evaluates to itself. -`qualid`-........+`qualname`+..........  A variable name; evaluates to its value in the current environment. @@ -812,9 +836,9 @@      Company any two values of numeric type for equality. -  ```op```+  ```symbol``` -    Use ``op``, which may be any non-operator function name, as an+    Use ``symbol``, which may be any non-operator function name, as an     infix operator.  ``x && y``@@ -1471,9 +1495,9 @@ -------  .. productionlist::-   mod_bind: "module" `id` `mod_param`* "=" [":" `mod_type_exp`] "=" `mod_exp`-   mod_param: "(" `id` ":" `mod_type_exp` ")"-   mod_type_bind: "module" "type" `id` "=" `mod_type_exp`+   mod_bind: "module" `name` `mod_param`* "=" [":" `mod_type_exp`] "=" `mod_exp`+   mod_param: "(" `name` ":" `mod_type_exp` ")"+   mod_type_bind: "module" "type" `name` "=" `mod_type_exp`  Futhark supports an ML-style higher-order module system.  *Modules* can contain types, functions, and other modules and module types.@@ -1515,7 +1539,7 @@ ~~~~~~~~~~~~~~~~~~  .. productionlist::-   mod_exp:   `qualid`+   mod_exp:   `qualname`           : | `mod_exp` ":" `mod_type_exp`           : | "\" "(" `mod_param`* ")" [":" `mod_type_exp`] "->" `mod_exp`           : | `mod_exp` `mod_exp`@@ -1527,8 +1551,8 @@ bindings produced by declarations (`dec`).  In particular, a module may contain other modules or module types. -``qualid``-..........+``qualname``+............  Evaluates to the module of the given name. @@ -1576,20 +1600,20 @@ ~~~~~~~~~~~~~~~~~~~~~~~  .. productionlist::-   mod_type_exp:   `qualid`+   mod_type_exp:   `qualname`              : | "{" `spec`* "}"-             : | `mod_type_exp` "with" `qualid` `type_param`* "=" `type`+             : | `mod_type_exp` "with" `qualname` `type_param`* "=" `type`              : | "(" `mod_type_exp` ")"-             : | "(" `id` ":" `mod_type_exp` ")" "->" `mod_type_exp`+             : | "(" `name` ":" `mod_type_exp` ")" "->" `mod_type_exp`              : | `mod_type_exp` "->" `mod_type_exp`   .. productionlist::-   spec:   "val" `id` `type_param`* ":" `type`-       : | "val" `binop` `type_param`* ":" `type`-       : | ("type" | "type^" | "type~") `id` `type_param`* "=" `type`-       : | ("type" | "type^" | "type~") `id` `type_param`*-       : | "module" `id` ":" `mod_type_exp`+   spec:   "val" `name` `type_param`* ":" `type`+       : | "val" `symbol` `type_param`* ":" `type`+       : | ("type" | "type^" | "type~") `name` `type_param`* "=" `type`+       : | ("type" | "type^" | "type~") `name` `type_param`*+       : | "module" `name` ":" `mod_type_exp`        : | "include" `mod_type_exp`        : | "#[" `attr` "]" `spec` @@ -1657,9 +1681,9 @@ ----------  .. productionlist::-   attr:   `id`+   attr:   `name`        : | `decimal`-       : | `id` "(" [`attr` ("," `attr`)*] ")"+       : | `name` "(" [`attr` ("," `attr`)*] ")"  An expression, declaration, pattern, or module type spec can be prefixed with an attribute, written as ``#[attr]``.  This may affect

@@ -1,6 +1,6 @@ cabal-version: 2.4 name:           futhark-version:        0.25.3+version:        0.25.4 synopsis:       An optimising compiler for a functional, array-oriented language.  description:    Futhark is a small programming language designed to be compiled to

@@ -55,7 +55,7 @@       =<< eIf         first_elem         (resultBodyM $ scanNeutral scan)-        (eBody $ map (`eIndex` prev) res_incl)+        (eBody $ map (`eIndex` [prev]) res_incl)    letTupExp desc $ Op $ Screma w [iota] (mapSOAC lam) 

@@ -80,7 +80,7 @@         ( buildBody_ $ do             j <- letSubExp "j" =<< toExp (pe64 w - (le64 i + 1))             y_s <- forM ys_adj $ \y_ ->-              letSubExp (baseString y_ ++ "_j") =<< eIndex y_ (eSubExp j)+              letSubExp (baseString y_ ++ "_j") =<< eIndex y_ [eSubExp j]             let zso = orderArgs s y_s             let ido = orderArgs s $ case_jac k sc idmat             pure $ subExpsRes $ concat $ zipWith (++) zso $ fmap concat ido@@ -89,10 +89,10 @@             j <- letSubExp "j" =<< toExp (pe64 w - (le64 i + 1))             j1 <- letSubExp "j1" =<< toExp (pe64 w - le64 i)             y_s <- forM ys_adj $ \y_ ->-              letSubExp (baseString y_ ++ "_j") =<< eIndex y_ (eSubExp j)+              letSubExp (baseString y_ ++ "_j") =<< eIndex y_ [eSubExp j]              let args =-                  map (`eIndex` eSubExp j) ys ++ map (`eIndex` eSubExp j1) xs+                  map (`eIndex` [eSubExp j]) ys ++ map (`eIndex` [eSubExp j1]) xs             lam_rs <- traverse (`eLambda` args) lams              let yso = orderArgs s $ subExpsRes y_s@@ -171,7 +171,7 @@        dj <-         traverse-          (\dd -> letExp (baseString dd ++ "_dj") =<< eIndex dd (eSubExp j))+          (\dd -> letExp (baseString dd ++ "_dj") =<< eIndex dd [eSubExp j])           ds        fmap varsRes . letTupExp "scan_contribs"@@ -182,9 +182,8 @@               lam <- mkScanAdjointLam ops scan_lam WrtSecond $ fmap Var dj                im1 <- letSubExp "im1" =<< toExp (le64 i - 1)-              ys_im1 <- forM ys $ \y -> do-                y_t <- lookupType y-                letSubExp (baseString y ++ "_last") $ BasicOp $ Index y $ fullSlice y_t [DimFix im1]+              ys_im1 <- forM ys $ \y ->+                letSubExp (baseString y <> "_im1") =<< eIndex y [eSubExp im1]                let args = map eSubExp $ ys_im1 ++ map (Var . paramName) par_x               eLambda lam args@@ -341,5 +340,5 @@       mkLambda [par_i] $ do         a <-           letExp "ys_bar_rev"-            =<< eIndex arr (toExp (pe64 n - le64 (paramName par_i) - 1))+            =<< eIndex arr [toExp (pe64 n - le64 (paramName par_i) - 1)]         pure [varRes a]

@@ -403,7 +403,7 @@   [LetBoundEntry rep] bindingEntries stm@(Let pat _ _) vtable = do   pat_elem <- patElems pat-  pure $ defBndEntry vtable pat_elem (Aliases.aliasesOf pat_elem) stm+  pure $ defBndEntry vtable pat_elem (expandAliases (Aliases.aliasesOf pat_elem) vtable) stm  adjustSeveral :: (Ord k) => (v -> v) -> [k] -> M.Map k v -> M.Map k v adjustSeveral f = flip $ foldl' $ flip $ M.adjust f@@ -449,35 +449,36 @@   SymbolTable rep insertStm stm vtable =   flip (foldl' $ flip consume) (namesToList stm_consumed) $-    flip (foldl' addRevAliases) (patElems $ stmPat stm) $-      insertEntries (zip names $ map LetBound $ bindingEntries stm vtable) vtable+    flip (foldl' addRevAliases) (zip names entries) $+      insertEntries (zip names $ map LetBound entries) vtable   where+    entries = bindingEntries stm vtable     names = patNames $ stmPat stm     stm_consumed = expandAliases (Aliases.consumedInStm stm) vtable-    addRevAliases vtable' pe =+    addRevAliases vtable' (name, LetBoundEntry {letBoundAliases = als}) =       vtable' {bindings = adjustSeveral update inedges $ bindings vtable'}       where-        inedges = namesToList $ expandAliases (Aliases.aliasesOf pe) vtable'+        inedges = namesToList $ expandAliases als vtable'         update e = e {entryType = update' $ entryType e}         update' (LetBound entry) =           LetBound             entry-              { letBoundAliases = oneName (patElemName pe) <> letBoundAliases entry+              { letBoundAliases = oneName name <> letBoundAliases entry               }         update' (FParam entry) =           FParam             entry-              { fparamAliases = oneName (patElemName pe) <> fparamAliases entry+              { fparamAliases = oneName name <> fparamAliases entry               }         update' (LParam entry) =           LParam             entry-              { lparamAliases = oneName (patElemName pe) <> lparamAliases entry+              { lparamAliases = oneName name <> lparamAliases entry               }         update' (FreeVar entry) =           FreeVar             entry-              { freeVarAliases = oneName (patElemName pe) <> freeVarAliases entry+              { freeVarAliases = oneName name <> freeVarAliases entry               }         update' e = e 

@@ -170,11 +170,7 @@  usageInExp :: (Aliased rep) => Exp rep -> UsageTable usageInExp (Apply _ args _ _) =-  mconcat-    [ mconcat $ map consumedUsage $ namesToList $ subExpAliases arg-      | (arg, d) <- args,-        d == Consume-    ]+  mconcat [consumedUsage v | (Var v, Consume) <- args] usageInExp e@Loop {} =   foldMap consumedUsage $ namesToList $ consumedInExp e usageInExp (Match _ cases defbody _) =

@@ -202,7 +202,7 @@     fprintf(ctx->log, "Allocating %lld bytes for %s in %s (currently allocated: %lld bytes).\n",             (long long) size,             desc, $string:spacedesc,-            ctx->$id:usagename);+            (long long) ctx->$id:usagename);   }    $items:alloc

@@ -351,9 +351,9 @@          sIf (phys_tid .<. n) in_bounds out_of_bounds +    sOp $ Imp.ErrorSync Imp.FenceLocal     sComment "Transpose scan inputs" $ do       forM_ (zip transposedArrays privateArrays) $ \(trans, priv) -> do-        sOp localBarrier         sFor "i" m $ \i -> do           sharedIdx <-             dPrimVE "sharedIdx" $@@ -364,7 +364,7 @@         sFor "i" m $ \i -> do           sharedIdx <- dPrimV "sharedIdx" $ kernelLocalThreadId constants * m + i           copyDWIMFix priv [sExt64 i] (Var trans) [sExt64 $ tvExp sharedIdx]-    sOp $ Imp.ErrorSync Imp.FenceLocal+        sOp localBarrier      sComment "Per thread scan" $ do       -- We don't need to touch the first element, so only m-1

@@ -417,12 +417,14 @@             BinOp LogOr less_than_zero greater_than_size   foldBinOp LogOr (constant False) =<< zipWithM checkDim ws is' --- | The array element at this index.-eIndex :: (MonadBuilder m) => VName -> m (Exp (Rep m)) -> m (Exp (Rep m))-eIndex arr i = do-  i' <- letSubExp "i" =<< i+-- | The array element at this index.  Returns array unmodified if+-- indexes are null (does not even need to be an array in that case).+eIndex :: (MonadBuilder m) => VName -> [m (Exp (Rep m))] -> m (Exp (Rep m))+eIndex arr [] = eSubExp $ Var arr+eIndex arr is = do+  is' <- mapM (letSubExp "i" =<<) is   arr_t <- lookupType arr-  pure $ BasicOp $ Index arr $ fullSlice arr_t [DimFix i']+  pure $ BasicOp $ Index arr $ fullSlice arr_t $ map DimFix is'  -- | The last element of the given array. eLast :: (MonadBuilder m) => VName -> m (Exp (Rep m))@@ -431,7 +433,7 @@   nm1 <-     letSubExp "nm1" . BasicOp $       BinOp (Sub Int64 OverflowUndef) n (intConst Int64 1)-  eIndex arr (eSubExp nm1)+  eIndex arr [eSubExp nm1]  -- | Construct an unspecified value of the given type. eBlank :: (MonadBuilder m) => Type -> m (Exp (Rep m))

@@ -594,7 +594,7 @@               TC.bad . TC.TypeError $                 "Array "                   <> prettyText v-                  <> " returned by function, but has nontrivial index function "+                  <> " returned by function, but has nontrivial index function:\n"                   <> prettyText ixfun  matchLoopResultMem ::

@@ -234,7 +234,7 @@ expand ::   (Eq num, IntegralExp num) => num -> num -> IxFun num -> Maybe (IxFun num) expand o p (IxFun lmad base) =-  let onDim ld = ld {LMAD.ldStride = LMAD.ldStride ld * p}+  let onDim ld = ld {LMAD.ldStride = p * LMAD.ldStride ld}       lmad' =         LMAD           (o + p * LMAD.offset lmad)

@@ -223,17 +223,14 @@  -- Then the general case. reshape lmad@(LMAD off dims) newshape = do-  let mid_dims = take (length dims) dims+  let base_stride = ldStride (last dims)+      no_zero_stride = all (\ld -> ldStride ld /= 0) dims+      strides_as_expected = lmad == iotaStrided off base_stride (shape lmad) -  guard $-    -- checking conditions (2)-    all (\(LMADDim s _) -> s /= 0) mid_dims-      && all-        (\(ld, se) -> ldStride ld == se)-        (zip dims (reverse $ scanl (*) 1 (reverse (tail (shape lmad)))))+  guard $ no_zero_stride && strides_as_expected -  let LMAD off' dims_sup = iota off newshape-  Just $ LMAD off' dims_sup+  Just $ iotaStrided off base_stride newshape+{-# NOINLINE reshape #-}  -- | Substitute a name with a PrimExp in an LMAD. substituteInLMAD ::@@ -255,6 +252,19 @@ rank :: LMAD num -> Int rank = length . shape +iotaStrided ::+  (IntegralExp num) =>+  -- | Offset+  num ->+  -- | Base Stride+  num ->+  -- | Shape+  [num] ->+  LMAD num+iotaStrided off s ns =+  let ss = tail $ reverse $ scanl (*) s $ reverse ns+   in LMAD off $ zipWith LMADDim ss ns+ -- | Generalised iota with user-specified offset. iota ::   (IntegralExp num) =>@@ -263,10 +273,8 @@   -- | Shape   [num] ->   LMAD num-iota off ns =-  let rk = length ns-      ss = reverse $ take rk $ scanl (*) 1 $ reverse ns-   in LMAD off $ zipWith LMADDim ss ns+iota off = iotaStrided off 1+{-# NOINLINE iota #-}  -- | Create an LMAD that is existential in everything. mkExistential :: Int -> Int -> LMAD (Ext a)@@ -517,6 +525,7 @@       ((.&&.) . uncurry dynamicEqualsLMADDim)       true       (zip (dims lmad1) (dims lmad2))+{-# NOINLINE dynamicEqualsLMAD #-}  -- | Returns true if two 'LMAD's are equivalent. --@@ -526,10 +535,9 @@   length (dims lmad1) == length (dims lmad2)     && offset lmad1 == offset lmad2     && map ldStride (dims lmad1) == map ldStride (dims lmad2)+{-# NOINLINE equivalent #-} --- | Is this is a row-major array?+-- | Is this is a row-major array with zero offset? isDirect :: (Eq num, IntegralExp num) => LMAD num -> Bool-isDirect (LMAD offset dims) =-  let strides_expected = reverse $ scanl (*) 1 $ reverse $ tail $ map ldShape dims-   in offset == 0-        && and (zipWith (==) (map ldStride dims) strides_expected)+isDirect lmad = lmad == iota 0 (map ldShape $ dims lmad)+{-# NOINLINE isDirect #-}

@@ -627,7 +627,7 @@       Simplify $ foldClosedForm (`ST.lookupExp` vtable) pat red_fun nes arrs simplifyClosedFormReduce _ _ _ _ = Skip --- For now we just remove singleton SOACs.+-- For now we just remove singleton SOACs and those with unroll attributes. simplifyKnownIterationSOAC ::   (Buildable rep, BuilderOps rep, HasSOAC rep) =>   TopDownRuleOp rep@@ -685,6 +685,19 @@        forM_ (zip (patNames pat) res) $ \(v, SubExpRes cs se) ->         certifying cs $ letBindNames [v] $ BasicOp $ SubExp se+--+simplifyKnownIterationSOAC _ pat aux op+  | Just (Screma (Constant (IntValue (Int64Value k))) arrs (ScremaForm [] [] map_lam)) <- asSOAC op,+    "unroll" `inAttrs` stmAuxAttrs aux = Simplify $ do+      arrs_elems <- fmap transpose . forM [0 .. k - 1] $ \i -> do+        map_lam' <- renameLambda map_lam+        eLambda map_lam' $ map (`eIndex` [eSubExp (constant i)]) arrs+      forM_ (zip3 (patNames pat) arrs_elems (lambdaReturnType map_lam)) $+        \(v, arr_elems, t) ->+          certifying (mconcat (map resCerts arr_elems)) $+            letBindNames [v] . BasicOp $+              ArrayLit (map resSubExp arr_elems) t+-- simplifyKnownIterationSOAC _ _ _ _ = Skip  data ArrayOp@@ -737,9 +750,11 @@   S.Set (Pat (LetDec rep), ArrayOp) arrayOps cs = mconcat . map onStm . stmsToList . bodyStms   where-    -- It is not safe to move everything out of branches (#1874);-    -- probably we need to put some more intelligence in here somehow.+    -- It is not safe to move everything out of branches (#1874) or+    -- loops (#2015); probably we need to put some more intelligence+    -- in here somehow.     onStm (Let _ _ Match {}) = mempty+    onStm (Let _ _ Loop {}) = mempty     onStm (Let pat aux e) =       case isArrayOp (cs <> stmAuxCerts aux) e of         Just op -> S.singleton (pat, op)

@@ -1342,7 +1342,7 @@   Rule rep -- Some SegOp results can be moved outside the SegOp, which can -- simplify further analysis.-bottomUpSegOp (vtable, used) (Pat kpes) dec segop = Simplify $ do+bottomUpSegOp (vtable, _used) (Pat kpes) dec segop = Simplify $ do   -- Iterate through the bindings.  For each, we check whether it is   -- in kres and can be moved outside.  If so, we remove it from kres   -- and kpes and make it a binding outside.  We have to be careful@@ -1353,20 +1353,16 @@     localScope (scopeOfSegSpace space) $       foldM distribute (kpes, kts, kres, mempty) kstms -  when-    (kpes' == kpes)-    cannotSimplify+  when (kpes' == kpes) cannotSimplify    kbody' <--    localScope (scopeOfSegSpace space) $-      mkKernelBodyM kstms' kres'+    localScope (scopeOfSegSpace space) $ mkKernelBodyM kstms' kres'    addStm $ Let (Pat kpes') dec $ Op $ segOp $ mk_segop kts' kbody'   where-    (kts, kbody@(KernelBody _ kstms kres), num_nonmap_results, mk_segop) =+    (kts, KernelBody _ kstms kres, num_nonmap_results, mk_segop) =       segOpGuts segop     free_in_kstms = foldMap freeIn kstms-    consumed_in_segop = consumedInKernelBody kbody     space = segSpace segop      sliceWithGtidsFixed stm@@ -1395,13 +1391,9 @@                 letBindNames [patElemName kpe'] . BasicOp . Index arr $                   Slice $                     outer_slice <> remaining_slice-          if (patElemName kpe `UT.isConsumed` used)-            || (arr `nameIn` consumed_in_segop)-            then do-              precopy <- newVName $ baseString (patElemName kpe) <> "_precopy"-              index kpe {patElemName = precopy}-              letBindNames [patElemName kpe] $ BasicOp $ Replicate mempty $ Var precopy-            else index kpe+          precopy <- newVName $ baseString (patElemName kpe) <> "_precopy"+          index kpe {patElemName = precopy}+          letBindNames [patElemName kpe] $ BasicOp $ Replicate mempty $ Var precopy           pure             ( kpes'',               kts'',

@@ -889,7 +889,8 @@         Just rexp -> onExps bound (unReplaced rexp) e         Nothing -> pure ()     onExps bound e (Var v _ _)-      | Just rexp <- lookup (qualLeaf v) named2 = onExps bound e (unReplaced rexp)+      | Just rexp <- lookup (qualLeaf v) named2 =+          onExps bound e (unReplaced rexp)     onExps bound e1 e2       | Just es <- similarExps e1 e2 =           mapM_ (uncurry $ onExps bound) es

@@ -473,7 +473,8 @@     lambdaReturnType map_lam == lambdaReturnType red_lam, -- No mapout arrays.     not $ null arrs,     all primType $ lambdaReturnType map_lam,-    all (primType . paramType) $ lambdaParams map_lam =+    all (primType . paramType) $ lambdaParams map_lam,+    not $ "unroll" `inAttrs` stmAuxAttrs (stmAux stm) =       Just (w, arrs, (red_comm, red_lam, red_nes, map_lam))   | otherwise =       Nothing

@@ -137,11 +137,9 @@   pure [Let pat aux $ Op $ ParOp par_op' op'] onMCOp stage pat aux (MC.OtherOp soac)   | sequentialise stage soac = do-      stms <- runBuilder_ $ FOT.transformSOAC pat soac-      fmap concat $-        localScope (scopeOf stms) $-          mapM (optimiseStm (onMCOp stage)) $-            stmsToList stms+      stms <- runBuilder_ $ auxing aux $ FOT.transformSOAC pat soac+      fmap concat . localScope (scopeOf stms) $+        mapM (optimiseStm (onMCOp stage)) (stmsToList stms)   | otherwise =       -- Still sequentialise whatever's inside.       pure <$> (Let pat aux . Op . MC.OtherOp <$> mapSOACM optimise soac)@@ -159,11 +157,9 @@ onHostOp :: Stage -> OnOp GPU onHostOp stage pat aux (GPU.OtherOp soac)   | sequentialise stage soac = do-      stms <- runBuilder_ $ FOT.transformSOAC pat soac-      fmap concat $-        localScope (scopeOf stms) $-          mapM (optimiseStm (onHostOp stage)) $-            stmsToList stms+      stms <- runBuilder_ $ auxing aux $ FOT.transformSOAC pat soac+      fmap concat . localScope (scopeOf stms) $+        mapM (optimiseStm (onHostOp stage)) (stmsToList stms)   | otherwise =       -- Still sequentialise whatever's inside.       pure <$> (Let pat aux . Op . GPU.OtherOp <$> mapSOACM optimise soac)

@@ -566,23 +566,39 @@   scope <- asksScope scopeForSOACs   distributeMapBodyStms acc . fmap (certify cs) . snd     =<< runBuilderT (dissectScrema pat w form arrs) scope-maybeDistributeStm (Let pat aux (BasicOp (Replicate (Shape (d : ds)) v))) acc-  | [t] <- patTypes pat = do-      tmp <- newVName "tmp"-      let rowt = rowType t-          newstm = Let pat aux $ Op $ Screma d [] $ mapSOAC lam-          tmpstm =-            Let (Pat [PatElem tmp rowt]) aux $ BasicOp $ Replicate (Shape ds) v-          lam =-            Lambda-              { lambdaReturnType = [rowt],-                lambdaParams = [],-                lambdaBody = mkBody (oneStm tmpstm) [varRes tmp]-              }-      maybeDistributeStm newstm acc-maybeDistributeStm stm@(Let _ aux (BasicOp (Replicate (Shape []) (Var stm_arr)))) acc =-  distributeSingleUnaryStm acc stm stm_arr $ \_ outerpat arr ->-    pure $ oneStm $ Let outerpat aux $ BasicOp $ Replicate mempty $ Var arr+maybeDistributeStm stm@(Let _ aux (BasicOp (Replicate shape (Var stm_arr)))) acc = do+  distributeSingleUnaryStm acc stm stm_arr $ \nest outerpat arr ->+    if shape == mempty+      then pure $ oneStm $ Let outerpat aux $ BasicOp $ Replicate mempty $ Var arr+      else runBuilder_ $ auxing aux $ do+        arr_t <- lookupType arr+        let arr_r = arrayRank arr_t+            nest_r = length (snd nest) + 1+            res_r = arr_r + shapeRank shape+        -- Move the to-be-replicated dimensions outermost.+        arr_tr <-+          letExp (baseString arr <> "_tr") . BasicOp $+            Rearrange ([nest_r .. arr_r - 1] ++ [0 .. nest_r - 1]) arr+        -- Replicate the now-outermost dimensions appropriately.+        arr_tr_rep <-+          letExp (baseString arr <> "_tr_rep") . BasicOp $+            Replicate shape (Var arr_tr)+        -- Move the replicated dimensions back where they belong.+        letBind outerpat . BasicOp $+          Rearrange ([res_r - nest_r .. res_r - 1] ++ [0 .. res_r - nest_r - 1]) arr_tr_rep+maybeDistributeStm (Let (Pat [pe]) aux (BasicOp (Replicate (Shape (d : ds)) v))) acc = do+  tmp <- newVName "tmp"+  let rowt = rowType $ patElemType pe+      newstm = Let (Pat [pe]) aux $ Op $ Screma d [] $ mapSOAC lam+      tmpstm =+        Let (Pat [PatElem tmp rowt]) aux $ BasicOp $ Replicate (Shape ds) v+      lam =+        Lambda+          { lambdaReturnType = [rowt],+            lambdaParams = [],+            lambdaBody = mkBody (oneStm tmpstm) [varRes tmp]+          }+  maybeDistributeStm newstm acc -- Opaques are applied to the full array, because otherwise they can -- drastically inhibit parallelisation in some cases. maybeDistributeStm stm@(Let (Pat [pe]) aux (BasicOp (Opaque _ (Var stm_arr)))) acc@@ -648,10 +664,9 @@     Just (kernels, res, nest, acc')       | map resSubExp res == map Var (patNames $ stmPat stm),         (outer, _) <- nest,-        [(arr_p, arr)] <- loopNestingParamsAndArrs outer,-        boundInKernelNest nest-          `namesIntersection` freeIn stm-          == oneName (paramName arr_p),+        [(_, arr)] <- loopNestingParamsAndArrs outer,+        boundInKernelNest nest `namesIntersection` freeIn stm+          == oneName stm_arr,         perfectlyMapped arr nest -> do           addPostStms kernels           let outerpat = loopNestingPat $ fst nest@@ -842,12 +857,8 @@   ((res_t, res), kstms) <- runBuilder $ do     -- Compute indexes into full array.     v' <--      certifying cs $-        letSubExp "v" $-          BasicOp $-            Index v $-              Slice $-                map (DimFix . Var) slice_gtids+      certifying cs . letSubExp "v" . BasicOp . Index v $+        Slice (map (DimFix . Var) slice_gtids)     slice_is <-       traverse (toSubExp "index") $         fixSlice (fmap pe64 slice) $

@@ -199,7 +199,7 @@     go bound b (Scalar (Record fields)) =       Scalar . Record <$> traverse (go bound b) fields     go bound b (Scalar (TypeVar as tn targs)) =-      Scalar <$> (TypeVar as tn <$> traverse (onTypeArg bound b) targs)+      Scalar <$> (TypeVar as tn <$> traverse (onTypeArg tn bound b) targs)     go bound b (Scalar (Sum cs)) =       Scalar . Sum <$> traverse (traverse (go bound b)) cs     go _ _ (Scalar (Prim t)) =@@ -213,10 +213,15 @@               Named p' -> S.insert p' bound               Unnamed -> bound -    onTypeArg bound b (TypeArgDim d) =+    onTypeArg _ bound b (TypeArgDim d) =       TypeArgDim <$> f bound b d-    onTypeArg bound b (TypeArgType t) =-      TypeArgType <$> go bound b t+    onTypeArg tn bound b (TypeArgType t) =+      TypeArgType <$> go bound b' t+      where+        b' =+          if qualLeaf tn == fst intrinsicAcc+            then b+            else PosParam  -- | Return the uniqueness of a type. uniqueness :: TypeBase shape Uniqueness -> Uniqueness@@ -411,7 +416,8 @@               <$> zipWithM (matchTypeArg bound) targs1 targs2         _ -> pure t1 -    matchTypeArg _ ta@TypeArgType {} _ = pure ta+    matchTypeArg bound (TypeArgType t1) (TypeArgType t2) =+      TypeArgType <$> matchDims' bound t1 t2     matchTypeArg bound (TypeArgDim x) (TypeArgDim y) =       TypeArgDim <$> onDims bound x y     matchTypeArg _ a _ = pure a

@@ -986,10 +986,15 @@ dimUses :: TypeBase Size u -> (Names, Names) dimUses = flip execState mempty . traverseDims f   where-    f bound _ (Var v _ _) | qualLeaf v `S.member` bound = pure ()-    f _ PosImmediate (Var v _ _) = modify ((S.singleton (qualLeaf v), mempty) <>)-    f _ PosParam (Var v _ _) = modify ((mempty, S.singleton (qualLeaf v)) <>)-    f _ _ _ = pure ()+    f bound pos e =+      case pos of+        PosImmediate ->+          modify ((fvVars fv, mempty) <>)+        PosParam ->+          modify ((mempty, fvVars fv) <>)+        PosReturn -> pure ()+      where+        fv = freeInExp e `freeWithout` bound  checkApply ::   SrcLoc ->@@ -1007,7 +1012,7 @@     argtype' <- normTypeFully argtype      -- Check whether this would produce an impossible return type.-    let (tp2_produced_dims, tp2_paramdims) = dimUses $ toStruct tp2'+    let (tp2_produced_dims, tp2_paramdims) = dimUses tp2'         problematic = S.fromList ext <> boundInsideType argtype'         problem = any (`S.member` problematic) (tp2_paramdims `S.difference` tp2_produced_dims)     when (not (S.null problematic) && problem) $ do

@@ -120,6 +120,7 @@         test_reshape_permute_iota,         test_slice_reshape_iota2,         test_reshape_slice_iota3,+        test_flatten_strided,         test_complex1,         test_complex2,         test_expand1,@@ -198,6 +199,14 @@               DimSlice 0 n 1             ]      in reshape (slice (iota [n, n, n, n]) slc) newdims++-- Tests flattening something that is strided - this can occur after+-- memory expansion.+test_flatten_strided :: [TestTree]+test_flatten_strided =+  singleton . testCase "reshape . fix . iota 3d" . compareOps $+    let slc = Slice [DimSlice 0 n 1, DimSlice 0 2 1, DimFix 1]+     in reshape (slice (iota [n, 2, n * n]) slc) [2 * 10]  test_complex1 :: [TestTree] test_complex1 =