| 1 |
-- | A simple index operation representation. Every operation corresponds to a |
| 2 |
-- constructor. |
| 3 |
module Futhark.IR.Mem.IxFun.Alg |
| 4 |
( IxFun (..), |
| 5 |
iota, |
| 6 |
offsetIndex, |
| 7 |
permute, |
| 8 |
reshape, |
| 9 |
coerce, |
| 10 |
slice, |
| 11 |
flatSlice, |
| 12 |
expand, |
| 13 |
shape, |
| 14 |
index, |
| 15 |
disjoint, |
| 16 |
) |
| 17 |
where |
| 18 |
|
| 19 |
import Data.List qualified as L |
| 20 |
import Data.Set qualified as S |
| 21 |
import Futhark.IR.Pretty () |
| 22 |
import Futhark.IR.Prop |
| 23 |
import Futhark.IR.Syntax |
| 24 |
( DimIndex (..), |
| 25 |
FlatDimIndex (..), |
| 26 |
FlatSlice (..), |
| 27 |
Slice (..), |
| 28 |
flatSliceDims, |
| 29 |
sliceDims, |
| 30 |
unitSlice, |
| 31 |
) |
| 32 |
import Futhark.Util.IntegralExp |
| 33 |
import Futhark.Util.Pretty |
| 34 |
import Prelude hiding (div, mod, span) |
| 35 |
|
| 36 |
type Shape num = [num] |
| 37 |
|
| 38 |
type Indices num = [num] |
| 39 |
|
| 40 |
type Permutation = [Int] |
| 41 |
|
| 42 |
data IxFun num |
| 43 |
= Direct (Shape num) |
| 44 |
| Permute (IxFun num) Permutation |
| 45 |
| Index (IxFun num) (Slice num) |
| 46 |
| FlatIndex (IxFun num) (FlatSlice num) |
| 47 |
| Reshape (IxFun num) (Shape num) |
| 48 |
| Coerce (IxFun num) (Shape num) |
| 49 |
| OffsetIndex (IxFun num) num |
| 50 |
| Expand num num (IxFun num) |
| 51 |
deriving (Eq, Show) |
| 52 |
|
| 53 |
instance (Pretty num) => Pretty (IxFun num) where |
| 54 |
pretty (Direct dims) = |
| 55 |
"Direct" <> parens (commasep $ map pretty dims) |
| 56 |
pretty (Permute fun perm) = pretty fun <> pretty perm |
| 57 |
pretty (Index fun is) = pretty fun <> pretty is |
| 58 |
pretty (FlatIndex fun is) = pretty fun <> pretty is |
| 59 |
pretty (Reshape fun oldshape) = |
| 60 |
pretty fun |
| 61 |
<> "->reshape" |
| 62 |
<> parens (pretty oldshape) |
| 63 |
pretty (Coerce fun oldshape) = |
| 64 |
pretty fun |
| 65 |
<> "->coerce" |
| 66 |
<> parens (pretty oldshape) |
| 67 |
pretty (OffsetIndex fun i) = |
| 68 |
pretty fun <> "->offset_index" <> parens (pretty i) |
| 69 |
pretty (Expand o p fun) = |
| 70 |
"expand(" <> pretty o <> "," <+> pretty p <> "," <+> pretty fun <> ")" |
| 71 |
|
| 72 |
iota :: Shape num -> IxFun num |
| 73 |
iota = Direct |
| 74 |
|
| 75 |
offsetIndex :: IxFun num -> num -> IxFun num |
| 76 |
offsetIndex = OffsetIndex |
| 77 |
|
| 78 |
permute :: IxFun num -> Permutation -> IxFun num |
| 79 |
permute = Permute |
| 80 |
|
| 81 |
slice :: IxFun num -> Slice num -> IxFun num |
| 82 |
slice = Index |
| 83 |
|
| 84 |
flatSlice :: IxFun num -> FlatSlice num -> IxFun num |
| 85 |
flatSlice = FlatIndex |
| 86 |
|
| 87 |
expand :: num -> num -> IxFun num -> IxFun num |
| 88 |
expand = Expand |
| 89 |
|
| 90 |
reshape :: IxFun num -> Shape num -> IxFun num |
| 91 |
reshape = Reshape |
| 92 |
|
| 93 |
coerce :: IxFun num -> Shape num -> IxFun num |
| 94 |
coerce = Reshape |
| 95 |
|
| 96 |
shape :: |
| 97 |
(IntegralExp num) => |
| 98 |
IxFun num -> |
| 99 |
Shape num |
| 100 |
shape (Direct dims) = |
| 101 |
dims |
| 102 |
shape (Permute ixfun perm) = |
| 103 |
rearrangeShape perm $ shape ixfun |
| 104 |
shape (Index _ how) = |
| 105 |
sliceDims how |
| 106 |
shape (FlatIndex ixfun how) = |
| 107 |
flatSliceDims how <> tail (shape ixfun) |
| 108 |
shape (Reshape _ dims) = |
| 109 |
dims |
| 110 |
shape (Coerce _ dims) = |
| 111 |
dims |
| 112 |
shape (OffsetIndex ixfun _) = |
| 113 |
shape ixfun |
| 114 |
shape (Expand _ _ ixfun) = |
| 115 |
shape ixfun |
| 116 |
|
| 117 |
index :: |
| 118 |
(Eq num, IntegralExp num) => |
| 119 |
IxFun num -> |
| 120 |
Indices num -> |
| 121 |
num |
| 122 |
index (Direct dims) is = |
| 123 |
sum $ zipWith (*) is slicesizes |
| 124 |
where |
| 125 |
slicesizes = drop 1 $ sliceSizes dims |
| 126 |
index (Permute fun perm) is_new = |
| 127 |
index fun is_old |
| 128 |
where |
| 129 |
is_old = rearrangeShape (rearrangeInverse perm) is_new |
| 130 |
index (Index fun (Slice js)) is = |
| 131 |
index fun (adjust js is) |
| 132 |
where |
| 133 |
adjust (DimFix j : js') is' = j : adjust js' is' |
| 134 |
adjust (DimSlice j _ s : js') (i : is') = j + i * s : adjust js' is' |
| 135 |
adjust _ _ = [] |
| 136 |
index (FlatIndex fun (FlatSlice offset js)) is = |
| 137 |
index fun $ sum (offset : zipWith f is js) : drop (length js) is |
| 138 |
where |
| 139 |
f i (FlatDimIndex _ s) = i * s |
| 140 |
index (Reshape fun newshape) is = |
| 141 |
let new_indices = reshapeIndex (shape fun) newshape is |
| 142 |
in index fun new_indices |
| 143 |
index (Coerce fun _) is = |
| 144 |
index fun is |
| 145 |
index (OffsetIndex fun i) is = |
| 146 |
case shape fun of |
| 147 |
d : ds -> |
| 148 |
index (Index fun (Slice (DimSlice i (d - i) 1 : map (unitSlice 0) ds))) is |
| 149 |
[] -> error "index: OffsetIndex: underlying index function has rank zero" |
| 150 |
index (Expand o p ixfun) is = |
| 151 |
o + p * index ixfun is |
| 152 |
|
| 153 |
allPoints :: (IntegralExp num, Enum num) => [num] -> [[num]] |
| 154 |
allPoints dims = |
| 155 |
let total = product dims |
| 156 |
strides = drop 1 $ L.reverse $ scanl (*) 1 $ L.reverse dims |
| 157 |
in map (unflatInd strides) [0 .. total - 1] |
| 158 |
where |
| 159 |
unflatInd strides x = |
| 160 |
fst $ |
| 161 |
foldl |
| 162 |
( \(res, acc) span -> |
| 163 |
(res ++ [acc `div` span], acc `mod` span) |
| 164 |
) |
| 165 |
([], x) |
| 166 |
strides |
| 167 |
|
| 168 |
disjoint :: (IntegralExp num, Ord num, Enum num) => IxFun num -> IxFun num -> Bool |
| 169 |
disjoint ixf1 ixf2 = |
| 170 |
let shp1 = shape ixf1 |
| 171 |
points1 = S.fromList $ allPoints shp1 |
| 172 |
allIdxs1 = S.map (index ixf1) points1 |
| 173 |
shp2 = shape ixf2 |
| 174 |
points2 = S.fromList $ allPoints shp2 |
| 175 |
allIdxs2 = S.map (index ixf2) points2 |
| 176 |
in S.disjoint allIdxs1 allIdxs2 |