General

Slots

C Interface

Basic Types

Symbols

Items

Values

General

The CRL2 library provides a framework for representing control flow graphs. The graphs can be read from a file, written to a file, and the library provides an interface for accessing and modifying information.

The top-level class of the CRL2 library is 'Crl'. It is a pure namespace class (although not implemented as a namespace in C++), that serves as an encapsulation of names and global functions. There are only static member functions, so it is not allowed to instanciate the 'Crl' class.

Anything inheriting 'Crl' has access to alternative names of types and classes where the class prefix 'Crl' is stripped.

The main class of dynamic data is 'CrlObject'. This class has several interesting functions that all sub-classes implement:

Further, comparison and hashing is implemented in the Object class.

Also, dynamic casting is implemented. For a given class Xyz, you can try to cast an object o to that cast by using o->as_Xyz(). If the object is of that type, you get the very same pointer back, but with the given static type, and if it is not of that type, you get NULL. These casts have a different name in C, namely the name of the class in uppercase-underbar notation with CRL_TRY_ prepended. Thus:

x= y->as_ValueUnsigned()

is the same as C:

x= CRL_TRY_VALUE_UNSIGNED (y)

There is a boolean variant with CRL_IS_ prepended for convenience.

If you know that an object is of type Xyz, then you can use o->cast_Xyz() to cast it to that type. This raises an assertion if the type was not really Xyz. In production code, the cast will be eliminated completely and replaced by a static C++ cast. The C name is simple the class name in uppercase-underbar notation with CRL_ prepended:

x= y->cast_ValueUnsigned()

is the same as C:

x= CRL_VALUE_UNSIGNED (y)

A common idiom is:

if (CrlValueUnsigned *x= y->as_ValueUnsigned()) {
    ... use x ...
}

And in C:

if (CRL_IS_VALUE_UNSIGNED (y)) {
    ... use CRL_VALUE_UNSIGNED(Y) ...
}

Slots

When objects store data, these stores are called slots. The access is via two functions for reading and writing the slot. E.g. the slot 'address of an Instruction is read with the function Instruction::address() and written with Instruction::set_address().

C Interface

The library is natively implemented in C++. A C interface is automatically generated, so the naming is very regular.

The basic principles are the same as in the GTK interface:

• all functions use a common prefix: crl_

• all functions encode the type of the 'self' pointer (the 'this' pointer in C++): crl_value_...

• C++ type names use capitalised notation: CrlValue.

• functions use lowercase-underbar notation: crl_routine_get_name

• checking type casts use uppercase-underbar notation and are otherwise identical to the type name: CRL_VALUE

For convenience and because the interface is automatically generated, so some more functions don't hurt, the following additional rules apply:

• inherited functions are available for all sub-classes that have this function. This reduces the amount of casting that is necessary and helps find bugs at compile time due to additional warnings about pointer type mismatches. E.g. crl_value_numeric_get_maximum exists and also the inherited version crl_value_range_get_maximum exists in the interface.

• As already mentioned, the casts also have a TRY variant.

• Type names are additionally available in the more C-like lowercase-underbar notation with a suffixed _t: crl_value_t is the same as CrlValue.

Every member function documentation in this reference manual will list both the C++ member function and the C function.

Basic Types

The following basic types exist in the CRL2 library:

The precise number of bits in crl_unsigned_t may increase in the future (but it may take some time until architectures and C compilers have larger native integer types...).

Symbols

Symbols are hashed strings. The type 'crl_symbol_t' is a typedef to 'char const *', so a symbol is also a string. The difference is that due to the hashing, symbols can be compared for equality with ==. strcmp() is not necessary.

Further, symbols provide much faster access to hash tables, so all hash tables from string to something will be indexed with symbols.

Note

the Erwin library provides a script 'makesymbol.pl', which allows you to statically allocate all literal symbols in your source code. Identifiers of the form 'sym_....' are gathered by the script and a nice include file is generated that lets you declare extern declarations and initialse them at program start.

For manually converting a string into a symbol, use crl_string2symbol().

Items

The control flow graphs are represented as 'items', namely graphs, routines, blocks, instructions, operations. Further, data items exist: 'data' and 'bytes'. To represent meta information, meta items exist: 'meta' and 'info'.

The CRL2 class hierarchy lists items under the abstract class 'CrlItem'. There is another sub-distinction between them: all those that can occur as part of a routine are in the 'CrlRoutineItem' class sub-hierarchy.

Items store their corresponding sub-items in slots, but usually provide additional access for appending, inserting and the like. E.g. a Routine has the slot 'blocks' and Graph has the slot 'routines'. This way, the main CFG structure is stored.

CRL2 items store additional information in generic attributes. Some of these also have an important meaning for the CFG structure, e.g., because they inform about missing edges; an information needed for safe analyses. See the "Attribute" section for a list of standard attributes.

These are arranged as a map from a symbol key to a value. The values in CRL2 are all part of the 'CrlValue' class sub-hierarchy.

Access to attributes is via a large set of convenient functions. The most basic ones are Item::find() and Item::set().

Because the access interface is so large, the special Section "Structure" gives a detailed introduction.

Values

CRL2 has a large number of possible values in order to make it easy to store arbitrary information in attribute values.

The most basic ones are CrlUnsigned, CrlSigned, CrlFloat, CrlSymbol and CrlString.

Structured values also exist. There are two main types: those indexed with some key and those encapsulating another value. The non-indexed structured values are CrlValueBox, which encapsulates a transparent Value (you can use this for installing a 'place holder' that will be filled in later) and CrlValueItem, which holds a pointer to an CrlItem. This way, Items can used as values in CRL2 and stored in attributes.

The indexed structures are currently:

- CrlValueVector: A resizable array of CrlValue. The implementation uses the Erwin type CrlVectorValue, so please don't confuse the two. The slot values() contains the storage structure.

Vectors can directly be indexed with a set of access functions. The most basic ones are append(), set() and nth().

Indices of vectors start with index 0.

For a full list of the access interface, see the Section "Structure".

CrlValueList

In the same way as CrlValueVector, this stores an integer indexed structure. Appending, setting and finding are implemented similarly as for the vector, only the implementation uses a map.

Special access for fast insertion with a crl_list_key_t is provided.

Note that CrlValueList uses the same CRL2 file syntax as CrlValueVector. Currently, there is no way to read a CrlValueList from a CRL2 file. This will change in the future by the use of attribute type declarations.

For a full list of the access interface, see the Section "Structure".

CrlValueMap

This is a map from Symbol to Value. It provides a very similar structure as the attribute maps stored at CrlItem. Like Item, the generic access functions are CrlValueMap::find() and CrlValueMap::set()

Again, for a full list of the access interface, see the Section "Structure".

CrlValueMapItemValue

This is another hash table structure, but indexed with Items. One example for using this is when storing a set of Items, which is often the need in applications.

The native access functions are CrlValueMapItemValue::find and CrlValueMapItemValue::set. Note that the native key is Item const * instead of crl_symbol_t as for CrlValueMap.

And again, for a full list of the access interface, see the Section "Structure".

Structure

In CRL2, it is often the case that objects provide structured access to a CrlValue. E.g. an Item has an attribute map, and CrlValue may be sub-structured as a map or vector or list.

In order to have a unified interface, the abstract type CrlStructure is the top-level type for all structured types in CRL2.

Basic Access

Simple reading and writing of values is available in two shades: with an indexing key or without. Items, ValueVector, ValueList, ValueMap, ... use a key, while ValueBox and ValueItem need no key.

The access interface was greatly improved and extended in version 1.2.x of the CRL2 library. Some functions are not available in older interfaces. The interface is downward compatible but in cases, where function invocations are used that always fail: those functions have been removed from the interface. See the Changes file for details.

Reading

Reading functions exist for several types of keys and for structures without keys. All the following functions return a CrlValue*. Please note that it does not always work to use this generic access. For full knowledge, you must also read the section about on-the-fly casting before using the read access interface!

Example

To get the 'ext' attribute of an operation, i.e., the vector of extensions of that operation, use:

op->find ("ext")

In case you have a symbol sym_ext, you can use for better efficiency:

op->find_sym (sym_ext)

Access is often nested. Due to the fact that the access functions are supported by all classes in the sub-hierarchy of CrlStructure, you can simply use a chain of accessing. E.g. to get the first extension of an operation, use:

op->find_sym (sym_ext)->nth (0)

All the access functions are NULL-safe, so in case find_sym() fails and returns NULL, nth(0) will still work without crashing and cleanly return NULL itself. This makes the chained access very simple to use.

A common idiom for recursing over all extensions is the following:

void recurse (CrlStructure *s)
{
    if (s == NULL) return;

    // do something on 's'

    // then recurse all extensions:
    CrlValue *e;
    crl_value_sequence_forall_values (s->find_sym ("ext"), e)
        recurse (e);
}

This function can be used on Values and Items alike, so to recurse over all extensions of an operation, use can now just say:

CrlOperation *op;
// ...
recurse (op)

Another thing is shown in this example: the iterator for any sequence. Again, it is NULL-safe, so if find_sym() returns NULL, it cleanly iterates 0 times. See the section "Iterators" for a list of iterators.

Writing

The following functions exist for writing a value of type Value* into a given structure:

All the above functions are available in a version that only writes values once, i.e., never overwrites a value. Just append _once or insert before the key type suffix:

poke_once
set_once
set_once_sym

The C functions work the same:

crl_structure_set_once_nth
crl_structure_set_once_val
crl_structure_set_once_itm

For resetting the valid, you can either pass 'NULL' to the above functions (but you cannot easily do this literally in C++ as will be described later -- the 'NULL' will be interpreted as 'new ValueUnsigned(0)' (yes, it will!)), but better use a special 'reset' family of functions:

Special Access

There are some special access functions:

• for checking whether a value is set: these use the same interface as 'find' and 'nth', but return bool (crl_bool_t in C). The functions are called:

  	Key Type		C++ Access Function		C Access Function
  	no key		CrlStructure::is_valid()		crl_structure_is_valid()
  	crl_signed_t		CrlStructure::has()		crl_structure_has_nth()
  	char const *		CrlStructure::has()		crl_structure_has()
  	crl_symbol_t		CrlStructure::has_sym()		crl_structure_has_sym()
  	CrlItem const *		CrlStructure::has()		crl_structure_has_itm()
  	CrlValue const *		has()		crl_structure_has_val()

• for checking whether a value is 'special'. A structure access location is special if the value is stored in a special way instead of in a Value* box. This is sometimes important for the parser which must then delay storage of such a key. Sometimes it is not possible to set special attributes twice or to reset or invalidate special attributes.

  For Items, special attributes can be queried dynamically with this family of functions. Those attributes stored directly in an Item's slot is a special attribute.

  These access functions use the same interface as 'is_valid' and 'has', but the functions are called 'is_valid_special' and 'is_special' instead.

Casting

Most of the time, the final information you are interested in when looking up a value is not a CrlValue*, but in fact something more basic, i.e. char const * or crl_unsigned_t or int.

The access interface provides a generic casting interface for a CrlStructure. Any CrlStructure can be asked to cast itself to basic types.

Due to the fact that this casting might not succeed, some functions return bool for success and output the wanted value via a reference. This is when the result type has no means of storing 'invalid', which is usually coded as 'NULL'. To avoid confusion, the following tables gives the full C++ prototype:

The following convenience functions can be used when you don't want to handle failure of a cast, but instead, it's ok not to be able to distinguish a casting failure from a value if 0. This makes some cases easier:

Please clearly distinguish the kind of casting described in this section from C++ casting, including dynamic casting with the Object::as_* member functions. The casting described in this section is more an 'exporting' to plain C types instead of a cast. E.g. get(unsigned_t) works perfectly on CrlValueSigned (it succeeds if the value is positive or 0), while as_ValueUnsigned() fails for that class (of course).

Distinguish exporting: C++:

crl_unsigned_t x;
if (val->get (x)) {
   // ... succeeds for ValueSigned if value is >= 0 ...
}

from dynamic casting: C++:

if (CrlValueUnsigned *x= val->as_ValueUnsigned()) {
   // ... always fails for val :: ValueSigned ...
}

Here's a table mapping the C++ names to C names (note that the prefix 'crl_structure' may be different when accessing a more special sub-class as usual):

The references are passed as pointers in C and the 'bool' result is 'crl_bool_t' instead.

On-the-Fly Casting

To provide a better interface to accessing structures and to also allow a more efficient approach of accessing, all the access functions are also available with on-the-fly input and result casting. Conversions of result include all the variants listed in Section "Casting". The suffixes appended to the base name 'get' can simply be appended to an access function to get the cast. Examples: there is 'find_bool', 'nth_item', etc.

As said, this casting is not only done to avoid typing, but also to make more efficient implementations possible. Therefore, a structure with a special attribute "external" that accesses the slot 'is_external', which is stored as a boolean, does not need to generate a Value* just to react to a find("external"). find("external") may return NULL in this case. However, find_bool("external") correctly accesses the special attribute.

Furthermore, it is planned to include more efficient Value objects, e.g. for storing large byte blocks natively as a vector of bytes. These vectors will return NULL when queried for 'nth(0)'. Only the function that does on-the-fly casting will succeed: 'nth_byte(0)'.

Structures will always provide all on-the-fly castings for result types that do not involve generation of new objects. Therefore, the potential ValueVectorByte above will also respond correctly to 'nth_int(0)'. Only 'nth(0)' will not work, since it will not generate a Value* just for returning the result. This would easily lead to memory leaks when newly generated result values are never collected and deallocated.

In general, do not use an access chain with a final cast: C++:

x->find("external")->get_bool()   // WRONG!

but always include the cast in the last access: C++:

x->find_bool("external")   // correct!

In a similar way as the result type, the values can be cast on the fly. Additional to the usual 'Value*', the following types are accepted by the access interface, exemplified with the 'set' function with integer key:

In contrast to the result casts, an imperfect invocation wrt. the stored type will never fail just because a new object is avoided to be created, but instead it will generate or cast the value on the fly of possible in some way. This is because the library can safely handle intermediate objects with reference counting, while in the result casting, memory leaks would be likely.

So you can insert an unsigned value into a map very easily: C++:

op->set_sym (sym_infeasible, 1)

C:

 crl_operation_set_sym_unsigned (op, sym_infeasible, 1)

Ordering of suffixes is by order of declaration of the type in the function prototype: the result comes first, then come the arguments: it is therefore 'find_bool_sym' and not 'find_sym_bool' for the function searching for a symbol key and casting the result to bool.

Note

Using 'set' with a value of NULL is strongly deprecated due to very strange overloading rules of C++. The desired behaviour would be that 'NULL' be interpreted as 'Value*' and in turn, the given value is removed from the map. Instead, the C++ standard clearly states that in the cast of the above overloading 'NULL' behaves like 'crl_unsigned_t', so in fact, the following code will set the attribute to 0 instead of deleting it:

op->set_sym (sym_name, NULL)  // clearly misleading!

Therefore, for a literal 'NULL', use the 'reset' method instead:

op->reset_sym (sym_name)  // this was intended.

If you have a variable of type Value*, it is perfectly good to invoke 'set' with NULL:

CrlValue *name;
// ...
op->set_sym (syn_name, name) // clears the attr if name==NULL

Iterators

FIXME: continue

Iterators use a similar syntax to normal loops in C and C++:

crl_vector_forall (vector, index, value) {
   // use index and value
}

Erwin Iterators

Erwin vector and list iterators for C++:

crl_vector_forall (vector, index, value)
crl_vector_forall_keys (vector, index)
crl_vector_forall_values (vector, value)
crl_vector_forall_ptr (vector, index, ptr_to_value)
crl_vector_forall_values_ptr (vector, ptr_to_value)
  // for modifying the vector elements during iteration

crl_vector_forall(_keys, _values, _values_ptr)_reverse
  // family for reversed iteration

crl_list_forall
  // ... same as above ...

The C equivalents code the full type, and you always must include the index for iteration. E.g. for crl_vector_value_t*, in C:

crl_vector_value_forall (vector, index, value)
crl_vector_value_forall_ptr (vector, index, ptr_to_value)
crl_vector_value_forall_reverse (vector, index, value)
crl_vector_value_forall_ptr_reverse (vector, index, ptr_to_value)

(For other types, there are according functions.)

Erwin unsorted map iterators for C++:

crl_map_forall (map, key, value)
crl_map_forall_keys (map, key)
crl_map_forall_values (map, value)
crl_map_forall_ptr (map, key, ptr_to_value)
crl_map_forall_values_ptr (map, ptr_to_value)

You need an explicit iterator in C:

crl_map_symbol_value_iterator_t iter;

crl_map_symbol_value_forall (map, iter, key, value)
crl_map_symbol_value_forall_ptr (map, iter, key, ptr_to_value)
crl_map_symbol_value_forall_values (map, iter, value)
crl_map_symbol_value_forall_values_ptr (map, iter, ptr_to_value)
crl_map_symbol_value_forall_keys (map, iter, key)

Erwin sorted map iterators are only available in C++:

crl_map_forall_sorted_by_key (map, key, value)
crl_map_forall_keys_sorted_by_key (map, key)
crl_map_forall_values_sorted_by_key (map, value)
crl_map_forall_ptr_sorted_by_key (map, key, ptr_to_value)
crl_map_forall_values_ptr_sorted_by_key (map, ptr_to_value)

The sorted iterators need to copy the whole map into a vector, which is then sorted and iterated, so this requires additional memory. Still, break and continue are safe to be used: these additional structures are automatically deallocated when the iteration is left.

The copying makes it possible to freely edit the map while iterating it. This editing is not allowed for the unsorted iterators: they will probably just crash if you try this.

All iterators can also be sorted by several criteria:

Further, all the sorted iterators exist in a _reversed variant; just add that very suffix to the iterator names.

Note that although the unsorted map iterators are unsorted, they are still deterministic: you get the same order if you perform the same operations before reaching a loop.

CRL2 Iterators

Iterators over enum ranges, both in C and C++:

crl_class_id_t class_id;
crl_class_id_forall (class_id)

crl_edge_type_t edge_type;
crl_edge_type_forall (edge_type)

crl_block_type_t block_type;
crl_block_type_forall (block_type)

crl_functor_type_t functor_type;
crl_functor_type_forall (functor_type)

crl_compression_t compression;
crl_compression_forall (compression)

The following CRL2 iterators are available in C++ only. In C, you need to get the Erwin structure and use the Erwin iterator instead. The CRL2 C++ convenience iterators are just a wrapper around this.

Iterator on sub-structures of objects in C++:

// A sequence can be ValueVector, ValueList, ValueApplication.
// The loop works on any Structure, it just might not iterate
// if the object is no sequence.  For ValueList, however, the
// performance of these iterators is very, very poor.
//
// A value in the following iterator can be
// Value*, bool, int, crl_unsigned_t, crl_signed_t, crl_symbol_t;
// the iterated value is tried to be casted appropriately.
crl_value_sequence_forall (sequence, index, value)
crl_value_sequence_forall_values (sequence, value)

// Specialised iterators for Values:
crl_value_list_forall_children (value_list, value)
    // If you know that a sequence is a list, please prefer this
    // special iterator, as the crl_value_sequence_forall iterators
    // are quadratic in complexity on lists, due to limited
    // knowledge of the underlying data structure.

// Iterators non-Value sequences:
crl_item_declaration_forall_attrs (item_decl, attr)

// Iterators for an Item:
crl_graph_forall_routines (graph, routine)
crl_graph_forall_datas (graph, data)
crl_graph_forall_metas (graph, data)

crl_routine_forall_blocks (routine, block)
crl_routine_forall_contexts (routine, context)

crl_block_forall_instructions(block, instruction)
crl_block_type_forall_outgoing(block, type, edge)     // type is input
crl_block_type_forall_incoming(block, type, edge)
crl_block_forall_type_and_outgoing(block, type, edge) // type is output
crl_block_forall_type_and_incoming(block, type, edge)
crl_block_forall_outgoing(block, edge)
crl_block_forall_incoming(block, edge)

crl_instruction_forall_operations(instruction, operation)

crl_data_forall_bytes(data, bytes)

crl_meta_forall_info(meta, info)

Convenience Indexing

Some conceptually scalar structures provide additional access to special slots via the generic access interface.

Some examples

ValueRange provides emulated attributes "minimum" and "maximum" via find_sym(). These attributes are read-only.

Actually, the whole ValueNumeric family has the "minimum" and "maximum" attributes: a ValueUnsigned will just return itself when used.

ValueApplication emulates the attributes "functor" and "type".

Check the documentation of a specific class to see whether there are any special attributes.