AccelerateHS / AccelerateHS/accelerate

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

Aberta
#471 2 comentários 0 reações 0 responsáveis Ver no GitHub
Linguagem predominante
Haskell
Estrelas
1k
Forks
135
Métricas de merge de PRs
Nenhum PR com merge em 30d

Descrição

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

Guia de contribuição

Nenhum guia de contribuição indexado para este repositório

Avaliação

Esta issue ainda não foi avaliada.

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.