2 * Copyright (c) 2018-2020 Inria
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * Definition of a dictionary based cache compressor. Each entry is compared
31 * against a dictionary to search for matches.
33 * The dictionary is composed of 32-bit entries, and the comparison is done
36 * The patterns are implemented as individual classes that have a checking
37 * function isPattern(), to determine if the data fits the pattern, and a
38 * decompress() function, which decompresses the contents of a pattern.
39 * Every new pattern must inherit from the Pattern class and be added to the
43 #ifndef __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__
44 #define __MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__
51 #include <type_traits>
54 #include "base/bitfield.hh"
55 #include "base/statistics.hh"
56 #include "base/types.hh"
57 #include "mem/cache/compressors/base.hh"
59 struct BaseDictionaryCompressorParams;
61 namespace Compressor {
63 class BaseDictionaryCompressor : public Base
66 /** Dictionary size. */
67 const std::size_t dictionarySize;
69 /** Number of valid entries in the dictionary. */
70 std::size_t numEntries;
72 struct DictionaryStats : public Stats::Group
74 const BaseDictionaryCompressor& compressor;
76 DictionaryStats(BaseStats &base_group,
77 BaseDictionaryCompressor& _compressor);
79 void regStats() override;
81 /** Number of data entries that were compressed to each pattern. */
82 Stats::Vector patterns;
86 * Trick function to get the number of patterns.
88 * @return The number of defined patterns.
90 virtual uint64_t getNumPatterns() const = 0;
93 * Get meta-name assigned to the given pattern.
95 * @param number The number of the pattern.
96 * @return The meta-name of the pattern.
98 virtual std::string getName(int number) const = 0;
101 typedef BaseDictionaryCompressorParams Params;
102 BaseDictionaryCompressor(const Params &p);
103 ~BaseDictionaryCompressor() = default;
107 * A template version of the dictionary compressor that allows to choose the
110 * @tparam The type of a dictionary entry (e.g., uint16_t, uint32_t, etc).
113 class DictionaryCompressor : public BaseDictionaryCompressor
116 /** Convenience typedef for a dictionary entry. */
117 typedef std::array<uint8_t, sizeof(T)> DictionaryEntry;
120 * Compression data for the dictionary compressor. It consists of a vector
125 // Forward declaration of a pattern
127 class UncompressedPattern;
130 template <T value, T mask>
131 class MaskedValuePattern;
132 template <T mask, int location>
133 class LocatedMaskedPattern;
134 template <class RepT>
135 class RepeatedValuePattern;
136 template <std::size_t DeltaSizeBits>
138 template <unsigned N>
139 class SignExtendedPattern;
142 * Create a factory to determine if input matches a pattern. The if else
143 * chains are constructed by recursion. The patterns should be explored
144 * sorted by size for correct behaviour.
146 template <class Head, class... Tail>
149 static std::unique_ptr<Pattern> getPattern(
150 const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
151 const int match_location)
153 // If match this pattern, instantiate it. If a negative match
154 // location is used, the patterns that use the dictionary bytes
155 // must return false. This is used when there are no dictionary
157 if (Head::isPattern(bytes, dict_bytes, match_location)) {
158 return std::unique_ptr<Pattern>(
159 new Head(bytes, match_location));
160 // Otherwise, go for next pattern
162 return Factory<Tail...>::getPattern(bytes, dict_bytes,
169 * Specialization to end the recursion. This must be called when all
170 * other patterns failed, and there is no choice but to leave data
171 * uncompressed. As such, this pattern must inherit from the uncompressed
174 template <class Head>
177 static_assert(std::is_base_of<UncompressedPattern, Head>::value,
178 "The last pattern must always be derived from the uncompressed "
181 static std::unique_ptr<Pattern>
182 getPattern(const DictionaryEntry& bytes,
183 const DictionaryEntry& dict_bytes, const int match_location)
185 return std::unique_ptr<Pattern>(new Head(bytes, match_location));
189 /** The dictionary. */
190 std::vector<DictionaryEntry> dictionary;
193 * Since the factory cannot be instantiated here, classes that inherit
194 * from this base class have to implement the call to their factory's
197 virtual std::unique_ptr<Pattern>
198 getPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
199 const int match_location) const = 0;
204 * @param data Data to be compressed.
205 * @return The pattern this data matches.
207 std::unique_ptr<Pattern> compressValue(const T data);
210 * Decompress a pattern into a value that fits in a dictionary entry.
212 * @param pattern The pattern to be decompressed.
213 * @return The decompressed word.
215 T decompressValue(const Pattern* pattern);
217 /** Clear all dictionary entries. */
218 virtual void resetDictionary();
221 * Add an entry to the dictionary.
223 * @param data The new entry.
225 virtual void addToDictionary(const DictionaryEntry data) = 0;
228 * Instantiate a compression data of the sub-class compressor.
230 * @return The new compression data entry.
232 virtual std::unique_ptr<DictionaryCompressor::CompData>
233 instantiateDictionaryCompData() const;
238 * @param chunks The cache line to be compressed.
239 * @return Cache line after compression.
241 std::unique_ptr<Base::CompressionData> compress(
242 const std::vector<Chunk>& chunks);
244 std::unique_ptr<Base::CompressionData> compress(
245 const std::vector<Chunk>& chunks,
246 Cycles& comp_lat, Cycles& decomp_lat) override;
248 using BaseDictionaryCompressor::compress;
250 void decompress(const CompressionData* comp_data, uint64_t* data) override;
253 * Turn a value into a dictionary entry.
255 * @param value The value to turn.
256 * @return A dictionary entry containing the value.
258 static DictionaryEntry toDictionaryEntry(T value);
261 * Turn a dictionary entry into a value.
263 * @param The dictionary entry to turn.
264 * @return The value that the dictionary entry contained.
266 static T fromDictionaryEntry(const DictionaryEntry& entry);
269 typedef BaseDictionaryCompressorParams Params;
270 DictionaryCompressor(const Params &p);
271 ~DictionaryCompressor() = default;
275 * The compressed data is composed of multiple pattern entries. To add a new
276 * pattern one should inherit from this class and implement isPattern() and
277 * decompress(). Then the new pattern must be added to the PatternFactory
278 * declaration in crescent order of size (in the DictionaryCompressor class).
281 class DictionaryCompressor<T>::Pattern
284 /** Pattern enum number. */
285 const int patternNumber;
287 /** Code associated to the pattern. */
290 /** Length, in bits, of the code and match location. */
291 const uint8_t length;
293 /** Number of unmatched bits. */
294 const uint8_t numUnmatchedBits;
296 /** Index representing the the match location. */
297 const int matchLocation;
299 /** Wether the pattern allocates a dictionary entry or not. */
304 * Default constructor.
306 * @param number Pattern number.
307 * @param code Code associated to this pattern.
308 * @param metadata_length Length, in bits, of the code and match location.
309 * @param num_unmatched_bits Number of unmatched bits.
310 * @param match_location Index of the match location.
312 Pattern(const int number, const uint64_t code,
313 const uint64_t metadata_length, const uint64_t num_unmatched_bits,
314 const int match_location, const bool allocate = true)
315 : patternNumber(number), code(code), length(metadata_length),
316 numUnmatchedBits(num_unmatched_bits),
317 matchLocation(match_location), allocate(allocate)
321 /** Default destructor. */
322 virtual ~Pattern() = default;
325 * Get enum number associated to this pattern.
327 * @return The pattern enum number.
329 int getPatternNumber() const { return patternNumber; };
332 * Get code of this pattern.
336 uint8_t getCode() const { return code; }
339 * Get the index of the dictionary match location.
341 * @return The index of the match location.
343 uint8_t getMatchLocation() const { return matchLocation; }
346 * Get size, in bits, of the pattern (excluding prefix). Corresponds to
347 * unmatched_data_size + code_length.
354 return numUnmatchedBits + length;
358 * Determine if pattern allocates a dictionary entry.
360 * @return True if should allocate a dictionary entry.
362 bool shouldAllocate() const { return allocate; }
365 * Extract pattern's information to a string.
367 * @return A string containing the relevant pattern metadata.
372 return csprintf("pattern %s (encoding %x, size %u bits)",
373 getPatternNumber(), getCode(), getSizeBits());
377 * Decompress the pattern. Each pattern has its own way of interpreting
380 * @param dict_bytes The bytes in the corresponding matching entry.
381 * @return The decompressed pattern.
383 virtual DictionaryEntry decompress(
384 const DictionaryEntry dict_bytes) const = 0;
388 class DictionaryCompressor<T>::CompData : public CompressionData
391 /** The patterns matched in the original line. */
392 std::vector<std::unique_ptr<Pattern>> entries;
395 ~CompData() = default;
398 * Add a pattern entry to the list of patterns.
400 * @param entry The new pattern entry.
402 virtual void addEntry(std::unique_ptr<Pattern>);
406 * A pattern containing the original uncompressed data. This should be the
407 * worst case of every pattern factory, where if all other patterns fail,
408 * an instance of this pattern is created.
411 class DictionaryCompressor<T>::UncompressedPattern
412 : public DictionaryCompressor<T>::Pattern
415 /** A copy of the original data. */
416 const DictionaryEntry data;
419 UncompressedPattern(const int number,
421 const uint64_t metadata_length,
422 const int match_location,
423 const DictionaryEntry bytes)
424 : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
425 sizeof(T) * 8, match_location, true),
431 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
432 const int match_location)
434 // An entry can always be uncompressed
439 decompress(const DictionaryEntry dict_bytes) const override
446 * A pattern that compares masked values against dictionary entries. If
447 * the masked dictionary entry matches perfectly the masked value to be
448 * compressed, there is a pattern match.
450 * For example, if the mask is 0xFF00 (that is, this pattern matches the MSB),
451 * the value (V) 0xFF20 is being compressed, and the dictionary contains
452 * the value (D) 0xFF03, this is a match (V & mask == 0xFF00 == D & mask),
453 * and 0x0020 is added to the list of unmatched bits.
455 * @tparam mask A mask containing the bits that must match.
459 class DictionaryCompressor<T>::MaskedPattern
460 : public DictionaryCompressor<T>::Pattern
463 static_assert(mask != 0, "The pattern's value mask must not be zero. Use "
464 "the uncompressed pattern instead.");
466 /** A copy of the bits that do not belong to the mask. */
470 MaskedPattern(const int number,
472 const uint64_t metadata_length,
473 const int match_location,
474 const DictionaryEntry bytes,
475 const bool allocate = true)
476 : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
477 popCount(static_cast<T>(~mask)), match_location, allocate),
478 bits(DictionaryCompressor<T>::fromDictionaryEntry(bytes) & ~mask)
483 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
484 const int match_location)
486 const T masked_bytes =
487 DictionaryCompressor<T>::fromDictionaryEntry(bytes) & mask;
488 const T masked_dict_bytes =
489 DictionaryCompressor<T>::fromDictionaryEntry(dict_bytes) & mask;
490 return (match_location >= 0) && (masked_bytes == masked_dict_bytes);
494 decompress(const DictionaryEntry dict_bytes) const override
496 const T masked_dict_bytes =
497 DictionaryCompressor<T>::fromDictionaryEntry(dict_bytes) & mask;
498 return DictionaryCompressor<T>::toDictionaryEntry(
499 bits | masked_dict_bytes);
504 * A pattern that compares masked values to a masked portion of a fixed value.
505 * If all the masked bits match the provided non-dictionary value, there is a
508 * For example, assume the mask is 0xFF00 (that is, this pattern matches the
509 * MSB), and we are searching for data containing only ones (i.e., the fixed
511 * If the value (V) 0xFF20 is being compressed, this is a match (V & mask ==
512 * 0xFF00 == 0xFFFF & mask), and 0x20 is added to the list of unmatched bits.
513 * If the value (V2) 0x0120 is being compressed, this is not a match
514 * ((V2 & mask == 0x0100) != (0xFF00 == 0xFFFF & mask).
516 * @tparam value The value that is being matched against.
517 * @tparam mask A mask containing the bits that must match the given value.
520 template <T value, T mask>
521 class DictionaryCompressor<T>::MaskedValuePattern
522 : public MaskedPattern<mask>
525 static_assert(mask != 0, "The pattern's value mask must not be zero.");
528 MaskedValuePattern(const int number,
530 const uint64_t metadata_length,
531 const int match_location,
532 const DictionaryEntry bytes,
533 const bool allocate = false)
534 : MaskedPattern<mask>(number, code, metadata_length, match_location,
540 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
541 const int match_location)
543 // Compare the masked fixed value to the value being checked for
544 // patterns. Since the dictionary is not being used the match_location
546 const T masked_bytes =
547 DictionaryCompressor<T>::fromDictionaryEntry(bytes) & mask;
548 return ((value & mask) == masked_bytes);
552 decompress(const DictionaryEntry dict_bytes) const override
554 return MaskedPattern<mask>::decompress(
555 DictionaryCompressor<T>::toDictionaryEntry(value));
560 * A pattern that narrows the MaskedPattern by allowing a only single possible
561 * dictionary entry to be matched against.
563 * @tparam mask A mask containing the bits that must match.
564 * @tparam location The index of the single entry allowed to match.
567 template <T mask, int location>
568 class DictionaryCompressor<T>::LocatedMaskedPattern
569 : public MaskedPattern<mask>
572 LocatedMaskedPattern(const int number,
574 const uint64_t metadata_length,
575 const int match_location,
576 const DictionaryEntry bytes,
577 const bool allocate = true)
578 : MaskedPattern<mask>(number, code, metadata_length, match_location,
584 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
585 const int match_location)
587 // Besides doing the regular masked pattern matching, the match
588 // location must match perfectly with this instance's
589 return (match_location == location) &&
590 MaskedPattern<mask>::isPattern(bytes, dict_bytes, match_location);
595 * A pattern that checks if dictionary entry sized values are solely composed
596 * of multiple copies of a single value.
598 * For example, if we are looking for repeated bytes in a 1-byte granularity
599 * (RepT is uint8_t), the value 0x3232 would match, however 0x3332 wouldn't.
601 * @tparam RepT The type of the repeated value, which must fit in a dictionary
605 template <class RepT>
606 class DictionaryCompressor<T>::RepeatedValuePattern
607 : public DictionaryCompressor<T>::Pattern
610 static_assert(sizeof(T) > sizeof(RepT), "The repeated value's type must "
611 "be smaller than the dictionary entry's type.");
613 /** The repeated value. */
617 RepeatedValuePattern(const int number,
619 const uint64_t metadata_length,
620 const int match_location,
621 const DictionaryEntry bytes,
622 const bool allocate = true)
623 : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
624 8 * sizeof(RepT), match_location, allocate),
625 value(DictionaryCompressor<T>::fromDictionaryEntry(bytes))
630 isPattern(const DictionaryEntry& bytes, const DictionaryEntry& dict_bytes,
631 const int match_location)
633 // Parse the dictionary entry in a RepT granularity, and if all values
634 // are equal, this is a repeated value pattern. Since the dictionary
635 // is not being used, the match_location is irrelevant
636 T bytes_value = DictionaryCompressor<T>::fromDictionaryEntry(bytes);
637 const RepT rep_value = bytes_value;
638 for (int i = 0; i < (sizeof(T) / sizeof(RepT)); i++) {
639 RepT cur_value = bytes_value;
640 if (cur_value != rep_value) {
643 bytes_value >>= 8 * sizeof(RepT);
649 decompress(const DictionaryEntry dict_bytes) const override
651 // The decompressed value is just multiple consecutive instances of
654 for (int i = 0; i < (sizeof(T) / sizeof(RepT)); i++) {
655 decomp_value <<= 8 * sizeof(RepT);
656 decomp_value |= value;
658 return DictionaryCompressor<T>::toDictionaryEntry(decomp_value);
663 * A pattern that checks whether the difference of the value and the dictionary
664 * entries' is below a certain threshold. If so, the pattern is successful,
665 * and only the delta bits need to be stored.
667 * For example, if the delta can only contain up to 4 bits, and the dictionary
668 * contains the entry 0xA231, the value 0xA232 would be compressible, and
669 * the delta 0x1 would be stored. The value 0xA249, on the other hand, would
670 * not be compressible, since its delta (0x18) needs 5 bits to be stored.
672 * @tparam DeltaSizeBits Size of a delta entry, in number of bits, which
673 * determines the threshold. Must always be smaller
674 * than the dictionary entry type's size.
677 template <std::size_t DeltaSizeBits>
678 class DictionaryCompressor<T>::DeltaPattern
679 : public DictionaryCompressor<T>::Pattern
682 static_assert(DeltaSizeBits < (sizeof(T) * 8),
683 "Delta size must be smaller than base size");
686 * The original value. In theory we should keep only the deltas, but
687 * the dictionary entry is not inserted in the dictionary before the
688 * call to the constructor, so the delta cannot be calculated then.
690 const DictionaryEntry bytes;
693 DeltaPattern(const int number,
695 const uint64_t metadata_length,
696 const int match_location,
697 const DictionaryEntry bytes)
698 : DictionaryCompressor<T>::Pattern(number, code, metadata_length,
699 DeltaSizeBits, match_location, false),
705 * Compares a given value against a base to calculate their delta, and
706 * then determines whether it fits a limited sized container.
708 * @param bytes Value to be compared against base.
709 * @param base_bytes Base value.
710 * @return Whether the value fits in the container.
713 isValidDelta(const DictionaryEntry& bytes,
714 const DictionaryEntry& base_bytes)
716 const typename std::make_signed<T>::type limit = DeltaSizeBits ?
717 mask(DeltaSizeBits - 1) : 0;
719 DictionaryCompressor<T>::fromDictionaryEntry(bytes);
721 DictionaryCompressor<T>::fromDictionaryEntry(base_bytes);
722 const typename std::make_signed<T>::type delta = value - base;
723 return (delta >= -limit) && (delta <= limit);
727 isPattern(const DictionaryEntry& bytes,
728 const DictionaryEntry& dict_bytes, const int match_location)
730 return (match_location >= 0) && isValidDelta(bytes, dict_bytes);
734 decompress(const DictionaryEntry dict_bytes) const override
741 * A pattern that checks whether the value is an N bits sign-extended value,
742 * that is, all the MSB starting from the Nth are equal to the (N-1)th bit.
744 * Therefore, if N = 8, and T has 16 bits, the values within the ranges
745 * [0x0000, 0x007F] and [0xFF80, 0xFFFF] would match this pattern.
747 * @tparam N The number of bits in the non-extended original value. It must
748 * fit in a dictionary entry.
751 template <unsigned N>
752 class DictionaryCompressor<T>::SignExtendedPattern
753 : public DictionaryCompressor<T>::Pattern
756 static_assert((N > 0) & (N <= (sizeof(T) * 8)),
757 "The original data's type size must be smaller than the dictionary's");
759 /** The non-extended original value. */
763 SignExtendedPattern(const int number,
765 const uint64_t metadata_length,
766 const DictionaryEntry bytes,
767 const bool allocate = false)
768 : DictionaryCompressor<T>::Pattern(number, code, metadata_length, N,
770 bits(fromDictionaryEntry(bytes) & mask(N))
775 isPattern(const DictionaryEntry& bytes,
776 const DictionaryEntry& dict_bytes, const int match_location)
778 const T data = DictionaryCompressor<T>::fromDictionaryEntry(bytes);
779 return data == sext<N>(data & mask(N));
783 decompress(const DictionaryEntry dict_bytes) const override
785 return toDictionaryEntry(sext<N>(bits));
789 } // namespace Compressor
791 #endif //__MEM_CACHE_COMPRESSORS_DICTIONARY_COMPRESSOR_HH__