Debian Codegraph @

rts/c/copy.h

raw
1 // Start of copy.h
2
3 // Cache-oblivious map-transpose function.
4 #define GEN_MAP_TRANSPOSE(NAME, ELEM_TYPE) \
5 static void map_transpose_##NAME \
6 (ELEM_TYPE* dst, ELEM_TYPE* src, \
7 int64_t k, int64_t m, int64_t n, \
8 int64_t cb, int64_t ce, int64_t rb, int64_t re) \
9 { \
10 int32_t r = re - rb; \
11 int32_t c = ce - cb; \
12 if (k == 1) { \
13 if (r <= 64 && c <= 64) { \
14 for (int64_t j = 0; j < c; j++) { \
15 for (int64_t i = 0; i < r; i++) { \
16 dst[(j + cb) * n + (i + rb)] = src[(i + rb) * m + (j + cb)]; \
17 } \
18 } \
19 } else if (c <= r) { \
20 map_transpose_##NAME(dst, src, k, m, n, cb, ce, rb, rb + r/2); \
21 map_transpose_##NAME(dst, src, k, m, n, cb, ce, rb + r/2, re); \
22 } else { \
23 map_transpose_##NAME(dst, src, k, m, n, cb, cb + c/2, rb, re); \
24 map_transpose_##NAME(dst, src, k, m, n, cb + c/2, ce, rb, re); \
25 } \
26 } else { \
27 for (int64_t i = 0; i < k; i++) { \
28 map_transpose_##NAME(dst + i * m * n, src + i * m * n, 1, m, n, cb, ce, rb, re); \
29 }\
30 } \
31 }
32
33 // Straightforward LMAD copy function.
34 #define GEN_LMAD_COPY_ELEMENTS(NAME, ELEM_TYPE) \
35 static void lmad_copy_elements_##NAME(int r, \
36 ELEM_TYPE* dst, int64_t dst_strides[r], \
37 ELEM_TYPE *src, int64_t src_strides[r], \
38 int64_t shape[r]) { \
39 if (r == 1) { \
40 for (int i = 0; i < shape[0]; i++) { \
41 dst[i*dst_strides[0]] = src[i*src_strides[0]]; \
42 } \
43 } else if (r > 1) { \
44 for (int i = 0; i < shape[0]; i++) { \
45 lmad_copy_elements_##NAME(r-1, \
46 dst+i*dst_strides[0], dst_strides+1, \
47 src+i*src_strides[0], src_strides+1, \
48 shape+1); \
49 } \
50 } \
51 } \
52
53 // Check whether this LMAD can be seen as a transposed 2D array. This
54 // is done by checking every possible splitting point.
55 static bool lmad_is_tr(int64_t *n_out, int64_t *m_out,
56 int r,
57 const int64_t strides[r],
58 const int64_t shape[r]) {
59 for (int i = 1; i < r; i++) {
60 int n = 1, m = 1;
61 bool ok = true;
62 int64_t expected = 1;
63 // Check strides before 'i'.
64 for (int j = i-1; j >= 0; j--) {
65 ok = ok && strides[j] == expected;
66 expected *= shape[j];
67 n *= shape[j];
68 }
69 // Check strides after 'i'.
70 for (int j = r-1; j >= i; j--) {
71 ok = ok && strides[j] == expected;
72 expected *= shape[j];
73 m *= shape[j];
74 }
75 if (ok) {
76 *n_out = n;
77 *m_out = m;
78 return true;
79 }
80 }
81 return false;
82 }
83
84 // This function determines whether the a 'dst' LMAD is row-major and
85 // 'src' LMAD is column-major. Both LMADs are for arrays of the same
86 // shape. Both LMADs are allowed to have additional dimensions "on
87 // top". Essentially, this function determines whether a copy from
88 // 'src' to 'dst' is a "map(transpose)" that we know how to implement
89 // efficiently. The LMADs can have arbitrary rank, and the main
90 // challenge here is checking whether the src LMAD actually
91 // corresponds to a 2D column-major layout by morally collapsing
92 // dimensions. There is a lot of looping here, but the actual trip
93 // count is going to be very low in practice.
94 //
95 // Returns true if this is indeed a map(transpose), and writes the
96 // number of arrays, and moral array size to appropriate output
97 // parameters.
98 static bool lmad_map_tr(int64_t *num_arrays_out, int64_t *n_out, int64_t *m_out,
99 int r,
100 const int64_t dst_strides[r],
101 const int64_t src_strides[r],
102 const int64_t shape[r]) {
103 int64_t rowmajor_strides[r];
104 rowmajor_strides[r-1] = 1;
105
106 for (int i = r-2; i >= 0; i--) {
107 rowmajor_strides[i] = rowmajor_strides[i+1] * shape[i+1];
108 }
109
110 // map_r will be the number of mapped dimensions on top.
111 int map_r = 0;
112 int64_t num_arrays = 1;
113 for (int i = 0; i < r; i++) {
114 if (dst_strides[i] != rowmajor_strides[i] ||
115 src_strides[i] != rowmajor_strides[i]) {
116 break;
117 } else {
118 num_arrays *= shape[i];
119 map_r++;
120 }
121 }
122
123 *num_arrays_out = num_arrays;
124
125 if (r==map_r) {
126 return false;
127 }
128
129 if (memcmp(&rowmajor_strides[map_r],
130 &dst_strides[map_r],
131 sizeof(int64_t)*(r-map_r)) == 0) {
132 return lmad_is_tr(n_out, m_out, r-map_r, src_strides+map_r, shape+map_r);
133 } else if (memcmp(&rowmajor_strides[map_r],
134 &src_strides[map_r],
135 sizeof(int64_t)*(r-map_r)) == 0) {
136 return lmad_is_tr(m_out, n_out, r-map_r, dst_strides+map_r, shape+map_r);
137 }
138 return false;
139 }
140
141 // Check if the strides correspond to row-major strides of *any*
142 // permutation of the shape. This is done by recursive search with
143 // backtracking. This is worst-case exponential, but hopefully the
144 // arrays we encounter do not have that many dimensions.
145 static bool lmad_contiguous_search(int checked, int64_t expected,
146 int r,
147 int64_t strides[r], int64_t shape[r], bool used[r]) {
148 for (int i = 0; i < r; i++) {
149 for (int j = 0; j < r; j++) {
150 if (!used[j] && strides[j] == expected && strides[j] >= 0) {
151 used[j] = true;
152 if (checked+1 == r ||
153 lmad_contiguous_search(checked+1, expected * shape[j], r, strides, shape, used)) {
154 return true;
155 }
156 used[j] = false;
157 }
158 }
159 }
160 return false;
161 }
162
163 // Does this LMAD correspond to an array with positive strides and no
164 // holes?
165 static bool lmad_contiguous(int r, int64_t strides[r], int64_t shape[r]) {
166 bool used[r];
167 for (int i = 0; i < r; i++) {
168 used[i] = false;
169 }
170 return lmad_contiguous_search(0, 1, r, strides, shape, used);
171 }
172
173 // Does this copy correspond to something that could be done with a
174 // memcpy()-like operation? I.e. do the LMADs actually represent the
175 // same in-memory layout and are they contiguous?
176 static bool lmad_memcpyable(int r,
177 int64_t dst_strides[r], int64_t src_strides[r], int64_t shape[r]) {
178 if (!lmad_contiguous(r, dst_strides, shape)) {
179 return false;
180 }
181 for (int i = 0; i < r; i++) {
182 if (dst_strides[i] != src_strides[i] && shape[i] != 1) {
183 return false;
184 }
185 }
186 return true;
187 }
188
189
190 static void log_copy(struct futhark_context* ctx,
191 const char *kind, const char *provenance,
192 int r,
193 int64_t dst_offset, int64_t dst_strides[r],
194 int64_t src_offset, int64_t src_strides[r],
195 int64_t shape[r]) {
196 if (ctx->logging) {
197 fprintf(ctx->log, "\n# Copy %s\n", kind);
198 if (provenance) { fprintf(ctx->log, "At: %s\n", provenance); }
199 fprintf(ctx->log, "Shape: ");
200 for (int i = 0; i < r; i++) { fprintf(ctx->log, "[%ld]", (long int)shape[i]); }
201 fprintf(ctx->log, "\n");
202 fprintf(ctx->log, "Dst offset: %ld\n", (long int)dst_offset);
203 fprintf(ctx->log, "Dst strides:");
204 for (int i = 0; i < r; i++) { fprintf(ctx->log, " %ld", (long int)dst_strides[i]); }
205 fprintf(ctx->log, "\n");
206 fprintf(ctx->log, "Src offset: %ld\n", (long int)src_offset);
207 fprintf(ctx->log, "Src strides:");
208 for (int i = 0; i < r; i++) { fprintf(ctx->log, " %ld", (long int)src_strides[i]); }
209 fprintf(ctx->log, "\n");
210 }
211 }
212
213 static void log_transpose(struct futhark_context* ctx,
214 int64_t k, int64_t n, int64_t m) {
215 if (ctx->logging) {
216 fprintf(ctx->log, "## Transpose\n");
217 fprintf(ctx->log, "Arrays : %ld\n", (long int)k);
218 fprintf(ctx->log, "X elements : %ld\n", (long int)m);
219 fprintf(ctx->log, "Y elements : %ld\n", (long int)n);
220 fprintf(ctx->log, "\n");
221 }
222 }
223
224 #define GEN_LMAD_COPY(NAME, ELEM_TYPE) \
225 static void lmad_copy_##NAME \
226 (struct futhark_context *ctx, int r, \
227 ELEM_TYPE* dst, int64_t dst_offset, int64_t dst_strides[r], \
228 ELEM_TYPE *src, int64_t src_offset, int64_t src_strides[r], \
229 int64_t shape[r]) { \
230 log_copy(ctx, "CPU to CPU", NULL, r, dst_offset, dst_strides, \
231 src_offset, src_strides, shape); \
232 int64_t size = 1; \
233 for (int i = 0; i < r; i++) { size *= shape[i]; } \
234 if (size == 0) { return; } \
235 int64_t k, n, m; \
236 if (lmad_map_tr(&k, &n, &m, \
237 r, dst_strides, src_strides, shape)) { \
238 log_transpose(ctx, k, n, m); \
239 map_transpose_##NAME \
240 (dst+dst_offset, src+src_offset, k, n, m, 0, n, 0, m); \
241 } else if (lmad_memcpyable(r, dst_strides, src_strides, shape)) { \
242 if (ctx->logging) {fprintf(ctx->log, "## Flat copy\n\n");} \
243 memcpy(dst+dst_offset, src+src_offset, size*sizeof(*dst)); \
244 } else { \
245 if (ctx->logging) {fprintf(ctx->log, "## General copy\n\n");} \
246 lmad_copy_elements_##NAME \
247 (r, \
248 dst+dst_offset, dst_strides, \
249 src+src_offset, src_strides, shape); \
250 } \
251 }
252
253 GEN_MAP_TRANSPOSE(1b, uint8_t)
254 GEN_MAP_TRANSPOSE(2b, uint16_t)
255 GEN_MAP_TRANSPOSE(4b, uint32_t)
256 GEN_MAP_TRANSPOSE(8b, uint64_t)
257
258 GEN_LMAD_COPY_ELEMENTS(1b, uint8_t)
259 GEN_LMAD_COPY_ELEMENTS(2b, uint16_t)
260 GEN_LMAD_COPY_ELEMENTS(4b, uint32_t)
261 GEN_LMAD_COPY_ELEMENTS(8b, uint64_t)
262
263 GEN_LMAD_COPY(1b, uint8_t)
264 GEN_LMAD_COPY(2b, uint16_t)
265 GEN_LMAD_COPY(4b, uint32_t)
266 GEN_LMAD_COPY(8b, uint64_t)
267
268 // End of copy.h