LLVM  8.0.1
Public Member Functions | Public Attributes | List of all members
llvm::lowertypetests::GlobalLayoutBuilder Struct Reference

This class implements a layout algorithm for globals referenced by bit sets that tries to keep members of small bit sets together. More...

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

Collaboration diagram for llvm::lowertypetests::GlobalLayoutBuilder:
Collaboration graph
[legend]

Public Member Functions

 GlobalLayoutBuilder (uint64_t NumObjects)
 
void addFragment (const std::set< uint64_t > &F)
 Add F to the layout while trying to keep its indices contiguous. More...
 

Public Attributes

std::vector< std::vector< uint64_t > > Fragments
 The computed layout. More...
 
std::vector< uint64_t > FragmentMap
 Mapping from object index to fragment index. More...
 

Detailed Description

This class implements a layout algorithm for globals referenced by bit sets that tries to keep members of small bit sets together.

This can significantly reduce bit set sizes in many cases.

It works by assembling fragments of layout from sets of referenced globals. Each set of referenced globals causes the algorithm to create a new fragment, which is assembled by appending each referenced global in the set into the fragment. If a referenced global has already been referenced by an fragment created earlier, we instead delete that fragment and append its contents into the fragment we are assembling.

By starting with the smallest fragments, we minimize the size of the fragments that are copied into larger fragments. This is most intuitively thought about when considering the case where the globals are virtual tables and the bit sets represent their derived classes: in a single inheritance hierarchy, the optimum layout would involve a depth-first search of the class hierarchy (and in fact the computed layout ends up looking a lot like a DFS), but a naive DFS would not work well in the presence of multiple inheritance. This aspect of the algorithm ends up fitting smaller hierarchies inside larger ones where that would be beneficial.

For example, consider this class hierarchy:

A B \ / | \ C D E

We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and bsE (E). If we laid out our objects by DFS traversing B followed by A, our layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to cover the only 4 objects in its hierarchy, but not for bsA as it needs to cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows:

Add bsC, fragments {{C}} Add bsD, fragments {{C}, {D}} Add bsE, fragments {{C}, {D}, {E}} Add bsA, fragments {{A, C}, {D}, {E}} Add bsB, fragments {{B, A, C, D, E}}

This layout is optimal for bsA, as it now only needs to cover two (i.e. 3 fewer) objects, at the cost of bsB needing to cover 1 more object.

The bit set lowering pass assigns an object index to each object that needs to be laid out, and calls addFragment for each bit set passing the object indices of its referenced globals. It then assembles a layout from the computed layout in the Fragments field.

Definition at line 127 of file LowerTypeTests.h.

Constructor & Destructor Documentation

◆ GlobalLayoutBuilder()

llvm::lowertypetests::GlobalLayoutBuilder::GlobalLayoutBuilder ( uint64_t  NumObjects)
inline

Definition at line 135 of file LowerTypeTests.h.

References F().

Member Function Documentation

◆ addFragment()

void GlobalLayoutBuilder::addFragment ( const std::set< uint64_t > &  F)

Add F to the layout while trying to keep its indices contiguous.

If a previously seen fragment uses any of F's indices, that fragment will be laid out inside F.

Definition at line 182 of file LowerTypeTests.cpp.

Referenced by selectJumpTableArmEncoding().

Member Data Documentation

◆ FragmentMap

std::vector<uint64_t> llvm::lowertypetests::GlobalLayoutBuilder::FragmentMap

Mapping from object index to fragment index.

Definition at line 133 of file LowerTypeTests.h.

◆ Fragments

std::vector<std::vector<uint64_t> > llvm::lowertypetests::GlobalLayoutBuilder::Fragments

The computed layout.

Each element of this vector contains a fragment of layout (which may be empty) consisting of object indices.

Definition at line 130 of file LowerTypeTests.h.


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