What's in a Fragment?

Tamarin-Tracing now has trees, which means any piece of code(A fragment) can become attached to any other part of a fragment. Tamarin also uses the context of the tree to optimize a fragment that is attached to the tree. Prior to this patch, every fragment was simply an independent piece of code. This post will deal with the structure of a tree and how each fragment is compiled/relates to other fragments.

Fragmento has a data structure entitled _frags:

Fragmento.h
DWB(FragmentMap*) _frags; /* map from ip -> Fragment ptr */
The DWB is related to the garbage collector. A FragmentMap is really just a sorted hash map. When you iterate over _frags, you get a pointer to a Fragment which is an anchor fragment. An anchor fragment is the first trace that is recorded and becomes the "main" trace where other traces can become attached too. If you look at the visualizer, they are the blue labeled nodes. A fragment is considered compiled if it has code attached to it. A fragment can be kept in the _frags hashmap even if no code is attached to it. This signifies that the trace recorder tried to record something, but failed.

Now lets take a look at the fragment data structure:

Fragmento.h
class Fragment {
LIns* spawnedFrom;
DWB(Fragment*) branches;
TraceKind kind;
NIns* _code;
}

struct SideExit
{
Fragment *target;
verbose_only( uint32_t sid; )
verbose_only(Fragment *from;)
};

Lir.h
class LIns {
SideExit *exit();
}

When a side exit is taken, the recording of a fragment is successful, and the fragment is successfully compiled, the newly established fragment is added to the main traces branches list which is a list of branches attached to the trace. The fragment also has a link of where it spawned from, which returns the SideExit data structure. This side exit contains pointers with target/from fragments. The from points to where the side exit is attached to. The target points to where the fragment ends at, which may be another side exit or the main anchor trace. Finally there is some information regarding what kind of fragment was generated.
Fragmento.h
enum TraceKind {
LoopTrace,
BranchTrace,
MergeTrace
};

The TraceKind signifies if it is a loop, merge, or cross fragment. A loop fragment means that the end of the fragment jumps back to a loop header. A merge fragment means that it merged two fragments into one. Finally, a cross fragment implies that instead of jumping back to its main trace, a fragment instead jumps to another "main" trace. For example, in this post, the fragment \10 Sunspider/bitops-nsieve-bits.js18 is a cross fragment which jumps to T9, even though it originated from T8.