| 1 |
module Futhark.Optimise.ArrayLayout.LayoutTests (tests) where |
| 2 |
|
| 3 |
import Data.Map.Strict qualified as M |
| 4 |
import Futhark.Analysis.AccessPattern |
| 5 |
import Futhark.Analysis.PrimExp |
| 6 |
import Futhark.FreshNames |
| 7 |
import Futhark.IR.GPU (GPU) |
| 8 |
import Futhark.IR.GPUTests () |
| 9 |
import Futhark.Optimise.ArrayLayout.Layout |
| 10 |
import Language.Futhark.Core |
| 11 |
import Test.Tasty |
| 12 |
import Test.Tasty.HUnit |
| 13 |
|
| 14 |
tests :: TestTree |
| 15 |
tests = |
| 16 |
testGroup |
| 17 |
"Layout" |
| 18 |
[commonPermutationEliminatorsTests] |
| 19 |
|
| 20 |
commonPermutationEliminatorsTests :: TestTree |
| 21 |
commonPermutationEliminatorsTests = |
| 22 |
testGroup |
| 23 |
"commonPermutationEliminators" |
| 24 |
[permutationTests, nestTests, dimAccessTests, constIndexElimTests] |
| 25 |
|
| 26 |
permutationTests :: TestTree |
| 27 |
permutationTests = |
| 28 |
testGroup "Permutations" $ |
| 29 |
do |
| 30 |
-- This isn't the way to test this, in reality we should provide realistic |
| 31 |
-- access patterns that might result in the given permutations. |
| 32 |
-- Luckily we only use the original access for one check atm. |
| 33 |
[ testCase (unwords [show perm, "->", show res]) $ |
| 34 |
commonPermutationEliminators perm [] @?= res |
| 35 |
| (perm, res) <- |
| 36 |
[ ([0], True), |
| 37 |
([1, 0], False), |
| 38 |
([0, 1], True), |
| 39 |
([0, 0], True), |
| 40 |
([1, 1], True), |
| 41 |
([1, 2, 0], False), |
| 42 |
([2, 0, 1], False), |
| 43 |
([0, 1, 2], True), |
| 44 |
([1, 0, 2], True), |
| 45 |
([2, 1, 0], True), |
| 46 |
([2, 2, 0], True), |
| 47 |
([2, 1, 1], True), |
| 48 |
([1, 0, 1], True), |
| 49 |
([0, 0, 0], True), |
| 50 |
([0, 1, 2, 3, 4], True), |
| 51 |
([1, 0, 2, 3, 4], True), |
| 52 |
([2, 3, 0, 1, 4], True), |
| 53 |
([3, 4, 2, 0, 1], True), |
| 54 |
([2, 3, 4, 0, 1], False), |
| 55 |
([1, 2, 3, 4, 0], False), |
| 56 |
([3, 4, 0, 1, 2], False) |
| 57 |
] |
| 58 |
] |
| 59 |
|
| 60 |
nestTests :: TestTree |
| 61 |
nestTests = testGroup "Nests" $ |
| 62 |
do |
| 63 |
let names = generateNames 2 |
| 64 |
[ testCase (unwords [args, "->", show res]) $ |
| 65 |
commonPermutationEliminators [1, 0] nest @?= res |
| 66 |
| (args, nest, res) <- |
| 67 |
[ ("[]", [], False), |
| 68 |
("[CondBodyName]", [CondBodyName] <*> names, False), |
| 69 |
("[SegOpName]", [SegOpName . SegmentedMap] <*> names, True), |
| 70 |
("[LoopBodyName]", [LoopBodyName] <*> names, False), |
| 71 |
("[SegOpName, CondBodyName]", [SegOpName . SegmentedMap, CondBodyName] <*> names, True), |
| 72 |
("[CondBodyName, LoopBodyName]", [CondBodyName, LoopBodyName] <*> names, False) |
| 73 |
] |
| 74 |
] |
| 75 |
|
| 76 |
dimAccessTests :: TestTree |
| 77 |
dimAccessTests = testGroup "DimAccesses" [] -- TODO: Write tests for the part of commonPermutationEliminators that checks the complexity of the DimAccesses. |
| 78 |
|
| 79 |
constIndexElimTests :: TestTree |
| 80 |
constIndexElimTests = |
| 81 |
testGroup |
| 82 |
"constIndexElimTests" |
| 83 |
[ testCase "gpu eliminates indexes with constant in any dim" $ do |
| 84 |
let primExpTable = |
| 85 |
M.fromList |
| 86 |
[ ("gtid_4", Just (LeafExp "n_4" (IntType Int64))), |
| 87 |
("i_5", Just (LeafExp "n_4" (IntType Int64))) |
| 88 |
] |
| 89 |
layoutTableFromIndexTable primExpTable accessTableGPU @?= mempty, |
| 90 |
testCase "gpu ignores when not last" $ do |
| 91 |
let primExpTable = |
| 92 |
M.fromList |
| 93 |
[ ("gtid_4", Just (LeafExp "gtid_4" (IntType Int64))), |
| 94 |
("gtid_5", Just (LeafExp "gtid_5" (IntType Int64))), |
| 95 |
("i_6", Just (LeafExp "i_6" (IntType Int64))) |
| 96 |
] |
| 97 |
layoutTableFromIndexTable primExpTable accessTableGPUrev |
| 98 |
@?= M.fromList |
| 99 |
[ ( SegmentedMap "mapres_1", |
| 100 |
M.fromList |
| 101 |
[ ( ("a_2", [], [0, 1, 2, 3]), |
| 102 |
M.fromList [("A_3", [2, 3, 0, 1])] |
| 103 |
) |
| 104 |
] |
| 105 |
) |
| 106 |
] |
| 107 |
] |
| 108 |
where |
| 109 |
accessTableGPU :: IndexTable GPU |
| 110 |
accessTableGPU = |
| 111 |
singleAccess |
| 112 |
[ singleParAccess 0 "gtid_4", |
| 113 |
DimAccess mempty Nothing, |
| 114 |
singleSeqAccess 1 "i_5" |
| 115 |
] |
| 116 |
|
| 117 |
accessTableGPUrev :: IndexTable GPU |
| 118 |
accessTableGPUrev = |
| 119 |
singleAccess |
| 120 |
[ singleParAccess 1 "gtid_4", |
| 121 |
singleParAccess 2 "gtid_5", |
| 122 |
singleSeqAccess 0 "i_5", |
| 123 |
singleSeqAccess 2 "gtid_4" |
| 124 |
] |
| 125 |
|
| 126 |
singleAccess :: [DimAccess rep] -> IndexTable rep |
| 127 |
singleAccess dims = |
| 128 |
M.fromList |
| 129 |
[ ( sgOp, |
| 130 |
M.fromList |
| 131 |
[ ( ("A_2", [], [0, 1, 2, 3]), |
| 132 |
M.fromList |
| 133 |
[ ( "a_3", |
| 134 |
dims |
| 135 |
) |
| 136 |
] |
| 137 |
) |
| 138 |
] |
| 139 |
) |
| 140 |
] |
| 141 |
where |
| 142 |
sgOp = SegmentedMap {vnameFromSegOp = "mapres_1"} |
| 143 |
|
| 144 |
singleParAccess :: Int -> VName -> DimAccess rep |
| 145 |
singleParAccess level name = |
| 146 |
DimAccess |
| 147 |
(M.singleton name $ Dependency level ThreadID) |
| 148 |
(Just name) |
| 149 |
|
| 150 |
singleSeqAccess :: Int -> VName -> DimAccess rep |
| 151 |
singleSeqAccess level name = |
| 152 |
DimAccess |
| 153 |
(M.singleton name $ Dependency level LoopVar) |
| 154 |
(Just name) |
| 155 |
|
| 156 |
generateNames :: Int -> [VName] |
| 157 |
generateNames count = do |
| 158 |
let (name, source) = newName blankNameSource "i_0" |
| 159 |
fst $ foldl f ([name], source) [1 .. count - 1] |
| 160 |
where |
| 161 |
f (names, source) _ = do |
| 162 |
let (name, source') = newName source (last names) |
| 163 |
(names ++ [name], source') |