1 
2 #define LLVM_LIBC_USE_BUILTIN_MEMCPY_INLINE 0
3 
4 #include "utils/UnitTest/Test.h"
5 #include <src/__support/CPP/Array.h>
6 #include <src/string/memory_utils/algorithm.h>
7 #include <src/string/memory_utils/backends.h>
8 
9 #include <sstream>
10 
11 namespace __llvm_libc {
12 
13 struct alignas(64) Buffer : cpp::Array<char, 128> {
14   bool contains(const char *ptr) const {
15     return ptr >= data() && ptr < (data() + size());
16   }
17   size_t getOffset(const char *ptr) const { return ptr - data(); }
18   void fill(char c) {
19     for (auto itr = begin(); itr != end(); ++itr)
20       *itr = c;
21   }
22 };
23 
24 static Buffer buffer1;
25 static Buffer buffer2;
26 static std::ostringstream LOG;
27 
28 struct TestBackend {
29   static constexpr bool IS_BACKEND_TYPE = true;
30 
31   template <typename T> static void log(const char *Action, const char *ptr) {
32     LOG << Action << "<" << sizeof(T) << "> ";
33     if (buffer1.contains(ptr))
34       LOG << "a[" << buffer1.getOffset(ptr) << "]";
35     else if (buffer2.contains(ptr))
36       LOG << "b[" << buffer2.getOffset(ptr) << "]";
37     LOG << "\n";
38   }
39 
40   template <typename T, Temporality TS, Aligned AS>
41   static T load(const T *src) {
42     log<T>((AS == Aligned::YES ? "LdA" : "LdU"),
43            reinterpret_cast<const char *>(src));
44     return Scalar64BitBackend::load<T, TS, AS>(src);
45   }
46 
47   template <typename T, Temporality TS, Aligned AS>
48   static void store(T *dst, T value) {
49     log<T>((AS == Aligned::YES ? "StA" : "StU"),
50            reinterpret_cast<const char *>(dst));
51     Scalar64BitBackend::store<T, TS, AS>(dst, value);
52   }
53 
54   template <typename T> static inline T splat(ubyte value) {
55     LOG << "Splat<" << sizeof(T) << "> " << (unsigned)value << '\n';
56     return Scalar64BitBackend::splat<T>(value);
57   }
58 
59   template <typename T> static inline uint64_t notEquals(T v1, T v2) {
60     LOG << "Neq<" << sizeof(T) << ">\n";
61     return Scalar64BitBackend::notEquals<T>(v1, v2);
62   }
63 
64   template <typename T> static inline int32_t threeWayCmp(T v1, T v2) {
65     LOG << "Diff<" << sizeof(T) << ">\n";
66     return Scalar64BitBackend::threeWayCmp<T>(v1, v2);
67   }
68 
69   template <size_t Size>
70   using getNextType = Scalar64BitBackend::getNextType<Size>;
71 };
72 
73 struct LlvmLibcAlgorithm : public testing::Test {
74   void SetUp() override {
75     LOG = std::ostringstream();
76     LOG << '\n';
77   }
78 
79   void fillEqual() {
80     buffer1.fill('a');
81     buffer2.fill('a');
82   }
83 
84   void fillDifferent() {
85     buffer1.fill('a');
86     buffer2.fill('b');
87   }
88 
89   const char *getTrace() {
90     trace_ = LOG.str();
91     return trace_.c_str();
92   }
93 
94   const char *stripComments(const char *expected) {
95     expected_.clear();
96     std::stringstream ss(expected);
97     std::string line;
98     while (std::getline(ss, line, '\n')) {
99       const auto pos = line.find('#');
100       if (pos == std::string::npos) {
101         expected_ += line;
102       } else {
103         auto log = line.substr(0, pos);
104         while (!log.empty() && std::isspace(log.back()))
105           log.pop_back();
106         expected_ += log;
107       }
108       expected_ += '\n';
109     }
110     return expected_.c_str();
111   }
112 
113   template <size_t Align = 1> SrcAddr<Align> buf1(size_t offset = 0) const {
114     return buffer1.data() + offset;
115   }
116   template <size_t Align = 1> SrcAddr<Align> buf2(size_t offset = 0) const {
117     return buffer2.data() + offset;
118   }
119   template <size_t Align = 1> DstAddr<Align> dst(size_t offset = 0) const {
120     return buffer1.data() + offset;
121   }
122   template <size_t Align = 1> SrcAddr<Align> src(size_t offset = 0) const {
123     return buffer2.data() + offset;
124   }
125 
126 private:
127   std::string trace_;
128   std::string expected_;
129 };
130 
131 using _8 = SizedOp<TestBackend, 8>;
132 
133 ///////////////////////////////////////////////////////////////////////////////
134 //// Testing fixed fized forward operations
135 ///////////////////////////////////////////////////////////////////////////////
136 
137 ///////////////////////////////////////////////////////////////////////////////
138 // Copy
139 
140 TEST_F(LlvmLibcAlgorithm, copy_1) {
141   SizedOp<TestBackend, 1>::copy(dst(), src());
142   EXPECT_STREQ(getTrace(), stripComments(R"(
143 LdU<1> b[0]
144 StU<1> a[0]
145 )"));
146 }
147 
148 TEST_F(LlvmLibcAlgorithm, copy_15) {
149   SizedOp<TestBackend, 15>::copy(dst(), src());
150   EXPECT_STREQ(getTrace(), stripComments(R"(
151 LdU<8> b[0]
152 StU<8> a[0]
153 LdU<4> b[8]
154 StU<4> a[8]
155 LdU<2> b[12]
156 StU<2> a[12]
157 LdU<1> b[14]
158 StU<1> a[14]
159 )"));
160 }
161 
162 TEST_F(LlvmLibcAlgorithm, copy_16) {
163   SizedOp<TestBackend, 16>::copy(dst(), src());
164   EXPECT_STREQ(getTrace(), stripComments(R"(
165 LdU<8> b[0]
166 StU<8> a[0]
167 LdU<8> b[8]
168 StU<8> a[8]
169 )"));
170 }
171 ///////////////////////////////////////////////////////////////////////////////
172 // Move
173 
174 TEST_F(LlvmLibcAlgorithm, move_1) {
175   SizedOp<TestBackend, 1>::move(dst(), src());
176   EXPECT_STREQ(getTrace(), stripComments(R"(
177 LdU<1> b[0]
178 StU<1> a[0]
179 )"));
180 }
181 
182 TEST_F(LlvmLibcAlgorithm, move_15) {
183   SizedOp<TestBackend, 15>::move(dst(), src());
184   EXPECT_STREQ(getTrace(), stripComments(R"(
185 LdU<8> b[0]
186 LdU<4> b[8]
187 LdU<2> b[12]
188 LdU<1> b[14]
189 StU<1> a[14]
190 StU<2> a[12]
191 StU<4> a[8]
192 StU<8> a[0]
193 )"));
194 }
195 
196 TEST_F(LlvmLibcAlgorithm, move_16) {
197   SizedOp<TestBackend, 16>::move(dst(), src());
198   EXPECT_STREQ(getTrace(), stripComments(R"(
199 LdU<8> b[0]
200 LdU<8> b[8]
201 StU<8> a[8]
202 StU<8> a[0]
203 )"));
204 }
205 
206 ///////////////////////////////////////////////////////////////////////////////
207 // set
208 
209 TEST_F(LlvmLibcAlgorithm, set_1) {
210   SizedOp<TestBackend, 1>::set(dst(), ubyte{42});
211   EXPECT_STREQ(getTrace(), stripComments(R"(
212 Splat<1> 42
213 StU<1> a[0]
214 )"));
215 }
216 
217 TEST_F(LlvmLibcAlgorithm, set_15) {
218   SizedOp<TestBackend, 15>::set(dst(), ubyte{42});
219   EXPECT_STREQ(getTrace(), stripComments(R"(
220 Splat<8> 42
221 StU<8> a[0]
222 Splat<4> 42
223 StU<4> a[8]
224 Splat<2> 42
225 StU<2> a[12]
226 Splat<1> 42
227 StU<1> a[14]
228 )"));
229 }
230 
231 TEST_F(LlvmLibcAlgorithm, set_16) {
232   SizedOp<TestBackend, 16>::set(dst(), ubyte{42});
233   EXPECT_STREQ(getTrace(), stripComments(R"(
234 Splat<8> 42
235 StU<8> a[0]
236 Splat<8> 42
237 StU<8> a[8]
238 )"));
239 }
240 
241 ///////////////////////////////////////////////////////////////////////////////
242 // different
243 
244 TEST_F(LlvmLibcAlgorithm, different_1) {
245   fillEqual();
246   SizedOp<TestBackend, 1>::isDifferent(buf1(), buf2());
247   EXPECT_STREQ(getTrace(), stripComments(R"(
248 LdU<1> a[0]
249 LdU<1> b[0]
250 Neq<1>
251 )"));
252 }
253 
254 TEST_F(LlvmLibcAlgorithm, different_15) {
255   fillEqual();
256   SizedOp<TestBackend, 15>::isDifferent(buf1(), buf2());
257   EXPECT_STREQ(getTrace(), stripComments(R"(
258 LdU<8> a[0]
259 LdU<8> b[0]
260 Neq<8>
261 LdU<4> a[8]
262 LdU<4> b[8]
263 Neq<4>
264 LdU<2> a[12]
265 LdU<2> b[12]
266 Neq<2>
267 LdU<1> a[14]
268 LdU<1> b[14]
269 Neq<1>
270 )"));
271 }
272 
273 TEST_F(LlvmLibcAlgorithm, different_15_no_shortcircuit) {
274   fillDifferent();
275   SizedOp<TestBackend, 15>::isDifferent(buf1(), buf2());
276   // If buffer compare isDifferent we continue to aggregate.
277   EXPECT_STREQ(getTrace(), stripComments(R"(
278 LdU<8> a[0]
279 LdU<8> b[0]
280 Neq<8>
281 LdU<4> a[8]
282 LdU<4> b[8]
283 Neq<4>
284 LdU<2> a[12]
285 LdU<2> b[12]
286 Neq<2>
287 LdU<1> a[14]
288 LdU<1> b[14]
289 Neq<1>
290 )"));
291 }
292 
293 TEST_F(LlvmLibcAlgorithm, different_16) {
294   fillEqual();
295   SizedOp<TestBackend, 16>::isDifferent(buf1(), buf2());
296   EXPECT_STREQ(getTrace(), stripComments(R"(
297 LdU<8> a[0]
298 LdU<8> b[0]
299 Neq<8>
300 LdU<8> a[8]
301 LdU<8> b[8]
302 Neq<8>
303 )"));
304 }
305 
306 ///////////////////////////////////////////////////////////////////////////////
307 // three_way_cmp
308 
309 TEST_F(LlvmLibcAlgorithm, three_way_cmp_eq_1) {
310   fillEqual();
311   SizedOp<TestBackend, 1>::threeWayCmp(buf1(), buf2());
312   // Buffer compare equal, returning 0 and no call to Diff.
313   EXPECT_STREQ(getTrace(), stripComments(R"(
314 LdU<1> a[0]
315 LdU<1> b[0]
316 Diff<1>
317 )"));
318 }
319 
320 TEST_F(LlvmLibcAlgorithm, three_way_cmp_eq_15) {
321   fillEqual();
322   SizedOp<TestBackend, 15>::threeWayCmp(buf1(), buf2());
323   // Buffer compare equal, returning 0 and no call to Diff.
324   EXPECT_STREQ(getTrace(), stripComments(R"(
325 LdU<8> a[0]
326 LdU<8> b[0]
327 Diff<8>
328 LdU<4> a[8]
329 LdU<4> b[8]
330 Diff<4>
331 LdU<2> a[12]
332 LdU<2> b[12]
333 Diff<2>
334 LdU<1> a[14]
335 LdU<1> b[14]
336 Diff<1>
337 )"));
338 }
339 
340 TEST_F(LlvmLibcAlgorithm, three_way_cmp_neq_15_shortcircuit) {
341   fillDifferent();
342   SizedOp<TestBackend, 16>::threeWayCmp(buf1(), buf2());
343   // If buffer compare isDifferent we stop early.
344   EXPECT_STREQ(getTrace(), stripComments(R"(
345 LdU<8> a[0]
346 LdU<8> b[0]
347 Diff<8>
348 )"));
349 }
350 
351 TEST_F(LlvmLibcAlgorithm, three_way_cmp_eq_16) {
352   fillEqual();
353   SizedOp<TestBackend, 16>::threeWayCmp(buf1(), buf2());
354   // Buffer compare equal, returning 0 and no call to Diff.
355   EXPECT_STREQ(getTrace(), stripComments(R"(
356 LdU<8> a[0]
357 LdU<8> b[0]
358 Diff<8>
359 LdU<8> a[8]
360 LdU<8> b[8]
361 Diff<8>
362 )"));
363 }
364 
365 ///////////////////////////////////////////////////////////////////////////////
366 //// Testing skip operations
367 ///////////////////////////////////////////////////////////////////////////////
368 
369 TEST_F(LlvmLibcAlgorithm, skip_and_set) {
370   Skip<11>::Then<SizedOp<TestBackend, 1>>::set(dst(), ubyte{42});
371   EXPECT_STREQ(getTrace(), stripComments(R"(
372 Splat<1> 42
373 StU<1> a[11]
374 )"));
375 }
376 
377 TEST_F(LlvmLibcAlgorithm, skip_and_different_1) {
378   Skip<11>::Then<SizedOp<TestBackend, 1>>::isDifferent(buf1(), buf2());
379   EXPECT_STREQ(getTrace(), stripComments(R"(
380 LdU<1> a[11]
381 LdU<1> b[11]
382 Neq<1>
383 )"));
384 }
385 
386 TEST_F(LlvmLibcAlgorithm, skip_and_three_way_cmp_8) {
387   Skip<11>::Then<SizedOp<TestBackend, 1>>::threeWayCmp(buf1(), buf2());
388   EXPECT_STREQ(getTrace(), stripComments(R"(
389 LdU<1> a[11]
390 LdU<1> b[11]
391 Diff<1>
392 )"));
393 }
394 
395 ///////////////////////////////////////////////////////////////////////////////
396 //// Testing tail operations
397 ///////////////////////////////////////////////////////////////////////////////
398 
399 TEST_F(LlvmLibcAlgorithm, tail_copy_8) {
400   Tail<_8>::copy(dst(), src(), 16);
401   EXPECT_STREQ(getTrace(), stripComments(R"(
402 LdU<8> b[8]
403 StU<8> a[8]
404 )"));
405 }
406 
407 TEST_F(LlvmLibcAlgorithm, tail_move_8) {
408   Tail<_8>::move(dst(), src(), 16);
409   EXPECT_STREQ(getTrace(), stripComments(R"(
410 LdU<8> b[8]
411 StU<8> a[8]
412 )"));
413 }
414 
415 TEST_F(LlvmLibcAlgorithm, tail_set_8) {
416   Tail<_8>::set(dst(), ubyte{42}, 16);
417   EXPECT_STREQ(getTrace(), stripComments(R"(
418 Splat<8> 42
419 StU<8> a[8]
420 )"));
421 }
422 
423 TEST_F(LlvmLibcAlgorithm, tail_different_8) {
424   fillEqual();
425   Tail<_8>::isDifferent(buf1(), buf2(), 16);
426   EXPECT_STREQ(getTrace(), stripComments(R"(
427 LdU<8> a[8]
428 LdU<8> b[8]
429 Neq<8>
430 )"));
431 }
432 
433 TEST_F(LlvmLibcAlgorithm, tail_three_way_cmp_8) {
434   fillEqual();
435   Tail<_8>::threeWayCmp(buf1(), buf2(), 16);
436   EXPECT_STREQ(getTrace(), stripComments(R"(
437 LdU<8> a[8]
438 LdU<8> b[8]
439 Diff<8>
440 )"));
441 }
442 
443 ///////////////////////////////////////////////////////////////////////////////
444 //// Testing HeadTail operations
445 ///////////////////////////////////////////////////////////////////////////////
446 
447 TEST_F(LlvmLibcAlgorithm, head_tail_copy_8) {
448   HeadTail<_8>::copy(dst(), src(), 16);
449   EXPECT_STREQ(getTrace(), stripComments(R"(
450 LdU<8> b[0]
451 StU<8> a[0]
452 LdU<8> b[8]
453 StU<8> a[8]
454 )"));
455 }
456 
457 ///////////////////////////////////////////////////////////////////////////////
458 //// Testing Loop operations
459 ///////////////////////////////////////////////////////////////////////////////
460 
461 TEST_F(LlvmLibcAlgorithm, loop_copy_one_iteration_and_tail) {
462   Loop<_8>::copy(dst(), src(), 10);
463   EXPECT_STREQ(getTrace(), stripComments(R"(
464 LdU<8> b[0]
465 StU<8> a[0] # covers 0-7
466 LdU<8> b[2]
467 StU<8> a[2] # covers 2-9
468 )"));
469 }
470 
471 TEST_F(LlvmLibcAlgorithm, loop_copy_two_iteration_and_tail) {
472   Loop<_8>::copy(dst(), src(), 17);
473   EXPECT_STREQ(getTrace(), stripComments(R"(
474 LdU<8> b[0]
475 StU<8> a[0] # covers 0-7
476 LdU<8> b[8]
477 StU<8> a[8] # covers 8-15
478 LdU<8> b[9]
479 StU<8> a[9] # covers 9-16
480 )"));
481 }
482 
483 TEST_F(LlvmLibcAlgorithm, loop_with_one_turn_is_inefficient_but_ok) {
484   Loop<_8>::copy(dst(), src(), 8);
485   EXPECT_STREQ(getTrace(), stripComments(R"(
486 LdU<8> b[0]
487 StU<8> a[0] # first iteration covers 0-7
488 LdU<8> b[0] # tail also covers 0-7 but since Loop is supposed to be used
489 StU<8> a[0] # with a sufficient number of iterations the tail cost is amortised
490 )"));
491 }
492 
493 TEST_F(LlvmLibcAlgorithm, loop_with_round_number_of_turn) {
494   Loop<_8>::copy(dst(), src(), 24);
495   EXPECT_STREQ(getTrace(), stripComments(R"(
496 LdU<8> b[0]
497 StU<8> a[0] # first iteration covers 0-7
498 LdU<8> b[8]
499 StU<8> a[8] # second iteration covers 8-15
500 LdU<8> b[16]
501 StU<8> a[16]
502 )"));
503 }
504 
505 TEST_F(LlvmLibcAlgorithm, dst_aligned_loop) {
506   Loop<_8>::copy(dst<16>(), src(), 23);
507   EXPECT_STREQ(getTrace(), stripComments(R"(
508 LdU<8> b[0]
509 StA<8> a[0] # store is aligned on 16B
510 LdU<8> b[8]
511 StA<8> a[8] # subsequent stores are aligned
512 LdU<8> b[15]
513 StU<8> a[15] # Tail is always unaligned
514 )"));
515 }
516 
517 TEST_F(LlvmLibcAlgorithm, aligned_loop) {
518   Loop<_8>::copy(dst<16>(), src<8>(), 23);
519   EXPECT_STREQ(getTrace(), stripComments(R"(
520 LdA<8> b[0] # load is aligned on 8B
521 StA<8> a[0] # store is aligned on 16B
522 LdA<8> b[8] # subsequent loads are aligned
523 StA<8> a[8] # subsequent stores are aligned
524 LdU<8> b[15] # Tail is always unaligned
525 StU<8> a[15] # Tail is always unaligned
526 )"));
527 }
528 
529 ///////////////////////////////////////////////////////////////////////////////
530 //// Testing Align operations
531 ///////////////////////////////////////////////////////////////////////////////
532 
533 TEST_F(LlvmLibcAlgorithm, align_dst_copy_8) {
534   Align<_8, Arg::Dst>::Then<Loop<_8>>::copy(dst(2), src(3), 31);
535   EXPECT_STREQ(getTrace(), stripComments(R"(
536 LdU<8> b[3]
537 StU<8> a[2] # First store covers unaligned bytes
538 LdU<8> b[9]
539 StA<8> a[8] # First aligned store
540 LdU<8> b[17]
541 StA<8> a[16] # Subsequent stores are aligned
542 LdU<8> b[25]
543 StA<8> a[24] # Subsequent stores are aligned
544 LdU<8> b[26]
545 StU<8> a[25] # Last store covers remaining bytes
546 )"));
547 }
548 
549 TEST_F(LlvmLibcAlgorithm, align_src_copy_8) {
550   Align<_8, Arg::Src>::Then<Loop<_8>>::copy(dst(2), src(3), 31);
551   EXPECT_STREQ(getTrace(), stripComments(R"(
552 LdU<8> b[3] # First load covers unaligned bytes
553 StU<8> a[2]
554 LdA<8> b[8] # First aligned load
555 StU<8> a[7]
556 LdA<8> b[16] # Subsequent loads are aligned
557 StU<8> a[15]
558 LdA<8> b[24] # Subsequent loads are aligned
559 StU<8> a[23]
560 LdU<8> b[26] # Last load covers remaining bytes
561 StU<8> a[25]
562 )"));
563 }
564 
565 } // namespace __llvm_libc
566