AccelerateHS / AccelerateHS/accelerate

[BUG] Imperfect shape query propagation in the presence of dead code

未关闭
#471 2 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
主要语言
Haskell
星标
1k
派生
135
PR 合并指标
30 天内没有已合并 PR

描述

**Description**
The fusion pipeline tries to express array shape queries in expressions (with the `shape` primitive) in terms of shapes of argument arrays if not doing so would prevent fusion. However, the algorithm seems to miss certain cases; the case I ran into involves a shape query of an array that is not used anywhere outside of that shape query (and is thus dead code).

**Steps to reproduce**
Consider the following code:
```haskell
import Data.Array.Accelerate

shapePropTest1 =
let a7 = use (fromList (Z :. (1 :: Int) :. (1 :: Int)) [5.0 :: Float])
a8 = map (\x0 -> T2 (x0 * x0) x0) a7
a9 = map (\(T2 x0 _) -> x0) a8
in zipWith (+)
(generate (shape a9) (\_ -> 1.0))
(map (\(T2 _ tup) -> tup) a8)

shapePropTest2 =
let a7 = use (fromList (Z :. (1 :: Int) :. (1 :: Int)) [5.0 :: Float])
a8 = map (\x0 -> T2 (x0 * x0) x0) a7
a9 = map (\(T2 x0 _) -> x0) a8
in zipWith (+)
(generate (shape a8) (\_ -> 1.0))
(map (\(T2 _ tup) -> tup) a8)

main :: IO ()
main = print shapePropTest1 >> print shapePropTest2
```
The only difference between these two programs is the argument to `shape`. Note that `a8` and `a9` have the same shape by definition of `map`.

The first program `show`s to:
```
let
a0 = map (\x0 -> T2 (x0 * x0) x0) (use (Matrix (Z :. 1 :. 1) [ 5.0]))
a1 = map (\(T2 x0 _) -> x0) a0
a2 = map (\(_, x0) -> x0) a0
in
generate
(let T2 x0 x1 = shape a2 T2 x2 x3 = shape a1 in T2 (min x2 x0) (min x3 x1))
(\(T2 x0 x1) -> 1.0 + a2 ! (T2 x0 x1))
```
The second program `show`s to:
```
let a0 = use (Matrix (Z :. 1 :. 1) [ 5.0])
in
generate
(let T2 x0 x1 = shape a0 T2 x2 x3 = shape a0 in T2 (min x2 x0) (min x3 x1))
(\(T2 x0 x1) -> 1.0 + a0 ! (T2 x0 x1))
```
The first program exhibits suboptimal fusion, even though it is equivalent to the second.

**Expected behaviour**
Both programs should fuse to the same result, eliminating all `map` calls.

**Your environment**
- Accelerate: `accelerate-1.3.0.0` on Hackage, or commit `162a779f`.
- Accelerate backend(s): n/a
- GHC: Stack LTS 16.12 (ghc 8.8.4)
- OS: Arch Linux

贡献指南

这个仓库没有索引到贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。