AccelerateHS / AccelerateHS/accelerate

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

Abierto
#471 2 comentarios 0 reacciones 0 asignados Ver en GitHub
Lenguaje dominante
Haskell
Estrellas
1k
Forks
135
Métricas de merge de PR
Sin PR fusionados en 30 d

Descripción

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

Guía de contribución

No hay ninguna guía de contribución indexada para este repositorio

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.