Properties, features and code processors

This chapter describes the facilities provided by OTAWA to hook information on the program representation and to exchange information between analyses composing the WCET calculation in a flexible and extensible way. Annotations, called properties, are hooked to the program representation items they apply to. The properties are consistently and logically grouped into features and analyses are abstracted as code processors: a mix of the analysis algorithm, list of required features and provided features.

The properties are the first-class citizens of the OTAWA framework used to annotate the program representation. The annotations form a simple and usable facility to attach/retrieve from the program representation some pieces of information. This section describes in details the use of annotations, also called properties.

A property is a triple formed by:

• an identifier (usually an object of the class otawa::AbstractIdentifier),
• the type of the stored data,
• the stored data itself.

The properties work as dynamic fields in the object they are hooked to. As C++ does not support this feature, OTAWA encapsulates the management of properties in a specific syntax based on the C++ operator overload ability. So, the syntax to use a property is based on operators working on identifiers and objects supporting properties, that are called property lists. To read a property which identifier is ID and hooked to list, one has to write:

  ID ( list )

To set a property, one has just to use the same syntax followed by the assignment operator = and the assigned expression. If the annotation is already hooked to the property list, its value is automatically replaced.

  ID ( list ) = expression ;

The property system allow hooking several properties with the same identifier to a list. The trick is to use the add() function of an identifier applied to a property list:

  ID ( list ).add( expression );

To retrieve properties with the same identifier, one has to use a very straight-forward C++-11 syntax as below:

  for(auto x: ID . all ( list ) )
    use(data);

The properties may also be removed using the remove() function of the identifier:

  ID ( list ) . remove ( ) ;

To test if a property is hooked to a property list, one can use the exists() function:

  if ( ID ( list ) . exists ( ) )
  	use ( ID ( list ) );

Whatever, accessing a property that is not defined in a property list, does not cause a crash but returns the default value associated with the property identifier.

Although the access time to OTAWA properties is longer than usual C++ member variables, the penalty is reduced thanks to a cache system that benefits from the temporal locality of accesses. The properties also have a slightly larger size in memory. Yet, these drawbacks are balanced by the gain in flexibility and usability to work on the program representation.

The work of properties is supported by the automatic conversion facilities of C++. Yet, from time to time, the type checking system may be not clever enough to use this conversion. Anyway, you can always obtain the value of property by prefixing the identifier with a “*” as below:

	* ID ( list )

This section has listed the main primitives used to handle properties. The following section will show how to declare identifiers objects.

An identifier is a global object used to identify properties hooked to property lists. As global objects, they must be declared in the .h header file to be used out of the current module and defined in the .cpp source file to be actually defined. In both files, the type of the stored data must be specified.

The following example shows how to declare in a header file an identifier called EXECUTION_TIME that stores a time expressed by a simple long long integer. Here, the extern C++ modifier ensures that the global object will not be defined in each source that includes the header file.

#include <otawa/prop.h>
 
extern p::id<long long> EXECUTION_TIME;

The definition of an identifier follows the usual rules of C++ but two arguments must be passed to the constructor: the string name of the identifier (possibly empty for anonymous identifier) and its default value. This default value is returned by the property accessor if the property has not been not assigned to a property list but read. It may be a valid default value or an invalid value to show that the property is not defined.

In our example, we specify a default value of -1 (invalid time) to show that the property is not set.

#include <otawa/prop.h>
 
p::id<long long> EXECUTION_TIME("EXECUTION_TIME", -1);

If the identifier is used as a static member of class named MyCLASS, it must be declared as follows:

#include <otawa/prop.h>
 
class MyClass: ... {
  ...
  static p::id<long long> EXECUTION_TIME;
  ...
};

and defined as below:

#include <otawa/prop.h>
 
p::id<long long> MyClass::EXECUTION_TIME("MyClass::EXECUTION_TIME", -1);

Specifying the type of the stored data when defining an identifier allows the type checking system of C++ to be applied to properties which might help to avoid a bunch of errors. The data type is also used to provide many automatic facilities like pretty printing, arguments scanning, serialization and so on, for usual scalar types.

To maintain consistency in naming, OTAWA advises to use capital letters for the identifier names (it recalls the constant used in the #define directives).

To support properties, a class has to inherit publicly from the otawa::PropList class.

#include <otawa/prop/PropList.h>
 
class MyClass: public PropList {
public:
  ...
};

This PropList has a really little memory footprint (a single pointer), making it useful even for small objects. Allocation and free of the properties is automatically handled by the PropList class and does not require any additional action from the new class.

A context, in OTAWA, is a family of execution paths made of functions, calls and loop iterations. Each of this type of context step is identified by the address that represents the function address, the instruction call address or the loop header address.

In C++, a context is represent by the class ContextualPath that is a list of ContextualStep. Contextual steps are pairs ($k$, $a$) where $a$ is the address and $k$ the type of the step:

• FUNCTION – to design a function context,
• CALL – to design a call context,
• FIRST_ITER – to design the first iteration of a loop,
• OTHER_ITER – to design all iteration except the first one.

For example, to design the context function f (address a1) calls (address a2) the function g (address a3), one can write:

	ContextualPath p;
	p.push(FUNCTION, a1);
	p.push(CALL, a2);
	p.push(FUNCTION, a3);

A contextual path is used to assign several values to an identifier depending on particular context. For example, a BB can have different execution times depending on its context. In the example below, a BB can be located in two contexts p1 and p2 with, respectively, times t1 and t2:

	ContextualPath p1;
	...
	ContextualPath p2;
	...
	BasicBlock *bb = ...;
 
	p1(ipet::TIME, bb) = t1;
	p2(ipet::TIME, bb) = t2;

The time can retrieved with a close syntax:

	cout << "time in context " << p1 << " is " << *p1(ipet::TIME, bb) << io::endl;

Notice that the contexts can be fuzzy (that is incomplete). For example, in the example below, p1 is less specific than p2 (missing CALL step) but as p1 covers the p2 case, the result is defined and equal to t1.

	ContextualPath p1;
	p.push(FUNCTION, a1);
	p.push(FUNCTION, a3);

	ContextualPath p2;
	p.push(FUNCTION, a1);
	p.push(CALL, a2);
	p.push(FUNCTION, a3);
	
	p1(ipet::TIME, bb) = t1;
	int t2 = p1(ipet::TIME, bb);
	ASSERT(t1 == t2); 

The contextual path, in its syntax to access properties, supports the same function as identifier: add(), remove(), exists(), etc.

Properties can store simple types as well as complex container types. For example, it is possible to declare an identifier of type Vector<BasicBlock *>:

	extern p::id<Vector<BasicBlock *> > MY_BB_COLLECTION;

Yet, one may face performance issues when defining such a property. A vector object with its content has first to be created and then copied in the property:

	Vector<BasicBlock *> bbs;
	/* fill the vector */
	MY_BB_COLLECTION(cfg) = bbs;

An alternative is to use a pointer to a vector, to build the object and to assign the property:

	extern p::id<Vector<BasicBlock *> *> MY_BB_COLLECTION;
	...
	Vector<BasicBlock *> *bbs = new Vector<BasicBlock *>();
	/* fill the vector */
	MY_BB_COLLECTION(cfg) = bbs;

This method works perfectly but have several drawbacks: (a) one has – and not to forget – to delete the vector object when the corresponding feature is invalidated and (b) pointer prevents the user of operator of a class although the following syntax can be used (notice the double “*”):

	Vector<BasicBlock *>& v = **MY_BB_COLLECTION(cfg);

For small collection of objects, OTAWA provides a better solution thanks to the class Bag illustrated below:

	p::id<Bag<BasicBlock *> > MY_BB_COLLECTION;
	...
	Vector<BasicBlock *> bbs;
	/* fill the vector */
	MY_BB_COLLECTION(cfg) = bbs;
	...
	Bag<BasicBlock *>& bag = MY_BB_COLLECTION(cfg);

A Bag basically behaves as an ELM Array (supporting indexed accesses, iterators, length(), etc) but prevent the copy of its content. When a bag is assigned to another bag, the former looses its content that is stolen by the latter (just a matter of pointer copy). In addition, bags are compatible with Vector class and steal the content of a vector passed as parameter to their constructor.

As OTAWA is developing, more and more property identifier were added and this drives quickly to a chaos on the number of identifiers, on their availability, etc. To prevent this, the properties are grouped into features. For example, the feature called LOOP_HEADERS_FEATURE ensures that the following properties are set:

• LOOP_HEADER is a boolean property put on all BB that are loop headers,
• BACK_EDGE is also a boolean property put on all edges that are loop back edges.

This sections explains how features are declared and used.

Like identifiers, features are basically global variables used as identifiers (and they extend AbstractIdentifier class). The main difference is that a feature can define a default analysis (code processor) to be called when it is required.

In the header file, .h, a feature is declared by:

#include <otawa/proc.h>
using namespace otawa;
 
extern p::feature MY_FEATURE;

In the source file, .cpp, the feature is declared by:

p::feature MY_FEATURE("MY_FEATURE", p::make<MyBuilder>());

Where MyBuilder is a code processor providing the feature ¹⁾.

For now, and for the sake of performances and simplicity, the only link between a feature and its property identifiers is only logic, that is, not materialized in the software. Yet, it is advised to provide a solid documentation of each feature listing the set of supported identifiers, the type of object they are hooked to and possibly identifying identifiers used as configuration by the feature. A feature is really a contract ensuring that some properties are set at the right place on the program representation.

Going on with the LOOP_HEADERS_FEATURE, the autodocumentation of OTAWA gives:

p::feature otawa::LOOP_HEADERS_FEATURE("otawa::LOOP_HEADERS_FEATURE", ...)

This feature ensures that all loop header are marked with a LOOP_HEADER property, and the back-edges are marked with a BACK_EDGE property.

Include: <otawa/cfg/features.h>

Properties

• LOOP_HEADER (BasicBlock)
• BACK_EDGE (Edge)

The features are managed by the WorkSpace class that records the provided features.

The following functions are available:

	WorkSpace *ws = ...;
 
	ws->require(MY_FEATURE);

The require() function ensures that the feature MY_FEATURE is built (its properties are set) in the current workspace. If the feature is already available, nothing is done. Otherwise, the default code processor of the feature is invoked. require() can take an additional parameter, a property list, to configure the way the feature will be built. Notice that a feature code processor can require other features that needs to be built in turn and this call may outcome into a chain of analyses performed on the workspace.

	if(ws->provides(MY_FEATURE))
		do_somehting_with_the_feature();

The function isProvided() on the WorkSpace is used to test if a feature is provided.

	ws->invalidate(MY_FEATURE);

The invalidate() function is used to remove a feature. This means that the passed feature will not be available any more and that all its properties are removed from the workspace and the program representation. As there may be dependencies between features due to the code processors, all dependent features are also removed (and the corresponding properties). Invalidation can be used to release resources occupied by feature or because a change in the configuration makes obsolete the corresponding feature.

Features can not be provided as is by an application: a code processor (described in the next section) is needed.

	class MyProcessor: public BBProcessor{
		//your code
 
		protected:
			void processBB(WorkSpace *ws, CFG *cfd, Block *bb) override{
				ws->require(SOME_FEATURE); // deprecated
			}
	}

A new type of feature appeared in OTAWA V2, the interfaced feature. This feature does not only provide a set of properties (passive data) but also code and calculation through an interface. Such a feature is declared by:

	class MyInterface {
		...
	};
 
	extern p::interfaced_feature<MyInterface> MY_INTERFACED_FEATURE;

The class MyInterface is used as an interface to access or compute the resources provided by the feature. To get the interface, once the feature is provided in a workspace, one has to write:

	WorkSpace *ws = ...;
 
	MyInterface *mi = MY_INTERFACED_FEATURE.get(ws);

For example, the OTAWA feature COLLECTED_CFG_FEATURE, that collects and builds the CFGs used to represent a real-time task, is declared as:

p::interfaced_feature<const CFGCollection> otawa::COLLECTED_CFG_FEATURE("otawa::COLLECTED_CFG_FEATURE", ...)

And, anyone can work on the CFGs using the code:

	#include <otawa/cfg/features.h>
	using namespace otawa;
 
	WorkSpace *ws = ...;
	ws->require(COLLECTED_CFG_FEATURE);
 
	const CFGCollection *coll = COLLECTED_CFG_FEATURE.get(ws); 
	for(auto cfg: *coll)
		work_on_cfg(cfg);