LLVM 17.0.0git

This class is used to build a byte array containing overlapping bit sets. More...
#include "llvm/Transforms/IPO/LowerTypeTests.h"
Public Types  
enum  { BitsPerByte = 8 } 
Public Member Functions  
ByteArrayBuilder ()  
void  allocate (const std::set< uint64_t > &Bits, uint64_t BitSize, uint64_t &AllocByteOffset, uint8_t &AllocMask) 
Allocate BitSize bits in the byte array where Bits contains the bits to set.  
Public Attributes  
std::vector< uint8_t >  Bytes 
The byte array built so far.  
uint64_t  BitAllocs [BitsPerByte] 
The number of bytes allocated so far for each of the bits.  
This class is used to build a byte array containing overlapping bit sets.
By loading from indexed offsets into the byte array and applying a mask, a program can test bits from the bit set with a relatively short instruction sequence. For example, suppose we have 15 bit sets to lay out:
A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits), F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits), L (4 bits), M (3 bits), N (2 bits), O (1 bit)
These bits can be laid out in a 16byte array like this:
Byte Offset 0123456789ABCDEF
Bit 7 HHHHHHHHHIIIIIII 6 GGGGGGGGGGJJJJJJ 5 FFFFFFFFFFFKKKKK 4 EEEEEEEEEEEELLLL 3 DDDDDDDDDDDDDMMM 2 CCCCCCCCCCCCCCNN 1 BBBBBBBBBBBBBBBO 0 AAAAAAAAAAAAAAAA
For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done in 12 machine instructions on x86, or 46 instructions on ARM.
This is a byte array, rather than (say) a 2byte array or a 4byte array, because for one thing it gives us better packing (the more bins there are, the less evenly they will be filled), and for another, the instruction sequences can be slightly shorter, both on x86 and ARM.
Definition at line 174 of file LowerTypeTests.h.
anonymous enum 
Enumerator  

BitsPerByte 
Definition at line 178 of file LowerTypeTests.h.

inline 
Definition at line 183 of file LowerTypeTests.h.
References BitAllocs.
void ByteArrayBuilder::allocate  (  const std::set< uint64_t > &  Bits, 
uint64_t  BitSize,  
uint64_t &  AllocByteOffset,  
uint8_t &  AllocMask  
) 
Allocate BitSize bits in the byte array where Bits contains the bits to set.
AllocByteOffset is set to the offset within the byte array and AllocMask is set to the bitmask for those bits. This uses the LPT (Longest Processing Time) multiprocessor scheduling algorithm to lay out the bits efficiently; the pass allocates bit sets in decreasing size order.
Definition at line 219 of file LowerTypeTests.cpp.
References B, BitAllocs, BitsPerByte, Bytes, and I.
uint64_t llvm::lowertypetests::ByteArrayBuilder::BitAllocs[BitsPerByte] 
The number of bytes allocated so far for each of the bits.
Definition at line 181 of file LowerTypeTests.h.
Referenced by allocate(), and ByteArrayBuilder().
std::vector<uint8_t> llvm::lowertypetests::ByteArrayBuilder::Bytes 
The byte array built so far.
Definition at line 176 of file LowerTypeTests.h.
Referenced by allocate().