This class is used to build a byte array containing overlapping bit sets. More...

#include "llvm/Transforms/IPO/LowerTypeTests.h"

Collaboration diagram for llvm::lowertypetests::ByteArrayBuilder:

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. More...

Public Attributes
std::vector< uint8_t >	Bytes
	The byte array built so far. More...

uint64_t	BitAllocs [BitsPerByte]
	The number of bytes allocated so far for each of the bits. More...

Detailed Description

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 16-byte 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 1-2 machine instructions on x86, or 4-6 instructions on ARM.

This is a byte array, rather than (say) a 2-byte array or a 4-byte 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 175 of file LowerTypeTests.h.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum

Enumerator
BitsPerByte

Definition at line 179 of file LowerTypeTests.h.

Constructor & Destructor Documentation

◆ ByteArrayBuilder()

llvm::lowertypetests::ByteArrayBuilder::ByteArrayBuilder ( )

inline

Definition at line 184 of file LowerTypeTests.h.

References llvm::lowertypetests::BitSetInfo::Bits, llvm::lowertypetests::BitSetInfo::BitSize, and llvm::Intrinsic::memset.

Member Function Documentation

◆ allocate()

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 211 of file LowerTypeTests.cpp.

References B, llvm::tgtok::Bit, llvm::lowertypetests::BitSetInfo::Bits, llvm::lowertypetests::BitSetInfo::BitSize, and I.

Member Data Documentation

◆ BitAllocs

uint64_t llvm::lowertypetests::ByteArrayBuilder::BitAllocs[BitsPerByte]

The number of bytes allocated so far for each of the bits.

Definition at line 182 of file LowerTypeTests.h.

◆ Bytes

std::vector<uint8_t> llvm::lowertypetests::ByteArrayBuilder::Bytes

The byte array built so far.

Definition at line 177 of file LowerTypeTests.h.

The documentation for this struct was generated from the following files:

include/llvm/Transforms/IPO/LowerTypeTests.h
lib/Transforms/IPO/LowerTypeTests.cpp

Public Types

Public Member Functions

Public Attributes