1 //===-- Pod structs to describe a memory function----------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #ifndef LLVM_LIBC_BENCHMARKS_AUTOMEMCPY_COMMON_H
10 #define LLVM_LIBC_BENCHMARKS_AUTOMEMCPY_COMMON_H
11
12 #include <climits>
13 #include <cstddef>
14 #include <llvm/ADT/ArrayRef.h>
15 #include <llvm/ADT/Hashing.h>
16 #include <llvm/ADT/Optional.h>
17 #include <llvm/ADT/StringRef.h>
18 #include <tuple>
19
20 namespace llvm {
21 namespace automemcpy {
22
23 // Boilerplate code to be able to sort and hash types.
24 #define COMPARABLE_AND_HASHABLE(T, ...) \
25 inline auto asTuple() const { return std::tie(__VA_ARGS__); } \
26 bool operator==(const T &O) const { return asTuple() == O.asTuple(); } \
27 bool operator<(const T &O) const { return asTuple() < O.asTuple(); } \
28 struct Hasher { \
29 std::size_t operator()(const T &K) const { \
30 return llvm::hash_value(K.asTuple()); \
31 } \
32 };
33
34 // Represents the maximum value for the size parameter of a memory function.
35 // This is an `int` so we can use it as an expression in Z3.
36 // It also allows for a more readable and compact representation when storing
37 // the SizeSpan in the autogenerated C++ file.
38 static constexpr int kMaxSize = INT_MAX;
39
40 // This mimics the `Arg` type in libc/src/string/memory_utils/elements.h without
41 // having to depend on it.
42 enum class AlignArg { _1, _2, ARRAY_SIZE };
43
44 // Describes a range of sizes.
45 // We use the begin/end representation instead of first/last to allow for empty
46 // range (i.e. Begin == End)
47 struct SizeSpan {
48 size_t Begin = 0;
49 size_t End = 0;
50
51 COMPARABLE_AND_HASHABLE(SizeSpan, Begin, End)
52 };
53
54 // Describes a contiguous region.
55 // In such a region all sizes are handled individually.
56 // e.g. with Span = {0, 2};
57 // if(size == 0) return Handle<0>();
58 // if(size == 1) return Handle<1>();
59 struct Contiguous {
60 SizeSpan Span;
61
62 COMPARABLE_AND_HASHABLE(Contiguous, Span)
63 };
64
65 // This struct represents a range of sizes over which to use an overlapping
66 // strategy. An overlapping strategy of size N handles all sizes from N to 2xN.
67 // The span may represent several contiguous overlaps.
68 // e.g. with Span = {16, 128};
69 // if(size >= 16 and size < 32) return Handle<Overlap<16>>();
70 // if(size >= 32 and size < 64) return Handle<Overlap<32>>();
71 // if(size >= 64 and size < 128) return Handle<Overlap<64>>();
72 struct Overlap {
73 SizeSpan Span;
74
75 COMPARABLE_AND_HASHABLE(Overlap, Span)
76 };
77
78 // Describes a region using a loop handling BlockSize bytes at a time. The
79 // remaining bytes of the loop are handled with an overlapping operation.
80 struct Loop {
81 SizeSpan Span;
82 size_t BlockSize = 0;
83
84 COMPARABLE_AND_HASHABLE(Loop, Span, BlockSize)
85 };
86
87 // Same as `Loop` but starts by aligning a buffer on `Alignment` bytes.
88 // A first operation handling 'Alignment` bytes is performed followed by a
89 // sequence of Loop.BlockSize bytes operation. The Loop starts processing from
90 // the next aligned byte in the chosen buffer. The remaining bytes of the loop
91 // are handled with an overlapping operation.
92 struct AlignedLoop {
93 Loop Loop;
94 size_t Alignment = 0; // Size of the alignment.
95 AlignArg AlignTo = AlignArg::_1; // Which buffer to align.
96
97 COMPARABLE_AND_HASHABLE(AlignedLoop, Loop, Alignment, AlignTo)
98 };
99
100 // Some processors offer special instruction to handle the memory function
101 // completely, we refer to such instructions as accelerators.
102 struct Accelerator {
103 SizeSpan Span;
104
105 COMPARABLE_AND_HASHABLE(Accelerator, Span)
106 };
107
108 // The memory functions are assembled out of primitives that can be implemented
109 // with regular scalar operations (SCALAR), with the help of vector or bitcount
110 // instructions (NATIVE) or by deferring it to the compiler (BUILTIN).
111 enum class ElementTypeClass {
112 SCALAR,
113 NATIVE,
114 BUILTIN,
115 };
116
117 // A simple enum to categorize which function is being implemented.
118 enum class FunctionType {
119 MEMCPY,
120 MEMCMP,
121 BCMP,
122 MEMSET,
123 BZERO,
124 };
125
126 // This struct describes the skeleton of the implementation, it does not go into
127 // every detail but is enough to uniquely identify the implementation.
128 struct FunctionDescriptor {
129 FunctionType Type;
130 Optional<Contiguous> Contiguous;
131 Optional<Overlap> Overlap;
132 Optional<Loop> Loop;
133 Optional<AlignedLoop> AlignedLoop;
134 Optional<Accelerator> Accelerator;
135 ElementTypeClass ElementClass;
136
COMPARABLE_AND_HASHABLEFunctionDescriptor137 COMPARABLE_AND_HASHABLE(FunctionDescriptor, Type, Contiguous, Overlap, Loop,
138 AlignedLoop, Accelerator, ElementClass)
139
140 inline size_t id() const { return llvm::hash_value(asTuple()); }
141 };
142
143 // Same as above but with the function name.
144 struct NamedFunctionDescriptor {
145 StringRef Name;
146 FunctionDescriptor Desc;
147 };
148
hash_value(const ArrayRef<T> & V)149 template <typename T> llvm::hash_code hash_value(const ArrayRef<T> &V) {
150 return llvm::hash_combine_range(V.begin(), V.end());
151 }
hash_value(const T & O)152 template <typename T> llvm::hash_code hash_value(const T &O) {
153 return llvm::hash_value(O.asTuple());
154 }
155
156 } // namespace automemcpy
157 } // namespace llvm
158
159 #endif /* LLVM_LIBC_BENCHMARKS_AUTOMEMCPY_COMMON_H */
160