Debian Codegraph @

src-testing/Futhark/IR/Mem/IxFun/Alg.hs

raw
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