AccelerateHS / AccelerateHS/accelerate

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

Đang mở
#471 2 bình luận 0 reaction 0 người được giao Xem trên GitHub
Ngôn ngữ chính
Haskell
Star
1k
Fork
135
Chỉ số merge pull request
Không có pull request nào được merge trong 30 ngày

Mô tả

**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

Hướng dẫn đóng góp

Chưa lập chỉ mục được hướng dẫn đóng góp cho kho mã nguồn này

Đánh giá

Issue này chưa được đánh giá.

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.