LLVM  6.0.0svn
Public Types | Public Member Functions | Public Attributes | List of all members
llvm::lowertypetests::ByteArrayBuilder Struct Reference

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:
Collaboration graph
[legend]

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 174 of file LowerTypeTests.h.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum
Enumerator
BitsPerByte 

Definition at line 178 of file LowerTypeTests.h.

Constructor & Destructor Documentation

◆ ByteArrayBuilder()

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

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 208 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 181 of file LowerTypeTests.h.

◆ Bytes

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

The byte array built so far.

Definition at line 176 of file LowerTypeTests.h.


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