Basic Attributes

AIS

Extensions

Generic Attributes

Operation & Extension

Operation

Instruction

Block

Routine

Global

Data & Bytes & Info & Meta

AbsInt aiT/StackAnalyzer Attributes

Block

Routine

Global

AbsInt aiT/StackAnalyzer User Attributes

Operation

Block

Routine

Global

Flow

PAG

Cache

The CRL2 framework uses a number of standard attributes for exchanging information. This document is an initial approach to document which attributes exist, what they mean, which applications writes them, and which one uses them.

Note that some attributes may be special, i.e., the CRL2 library takes special care of them. This may either be due to the need for interpretation in the library, or because there is special CRL file syntax for them (usually to improve readability), or because the attributes are a special conceptual part of the CRL structure (e.g. the address of an instruction).

For special attributes, the CRL2 library provides member functions for direct access of the attribute values. These should be preferred over the generic Structure::find_sym() interface (although there is transparent access to them via that interface, too).

Please check the Items' documentation about which special attributes exist. Typically, there is a slot for storing the special attribute.

Note

When using the generic Structure::find_sym interface to access special attributes, you must use the result casting versions that output the correct type (e.g. find_sym_bool) and not those that return a generic CrlValue*. This is because the CRL2 library interface may change in the future without prior notice so that only the result casting versions return a value while the generic ones fail. This will be included in future library versions to improve overall performance and to avoid generating Values on the fly.

Further Note

In the following, attributes are often specified to be ranges. Do not rely on this exact type! For efficiency reasons, a plain scalar number (Unsigned, Signed or Float) may be used. So always use the generic interface ValueNumeric::minimum()/maximum() to retrieve the value instead of casting ta ValueRange!

AIS

Many of the user attributes will have AIS annotations that lead to those attributes. These are meant to be examples. For a full AIS syntax specification, please refer to the AbsInt manuals.

Extensions

In CRL2, resource information at operations can be stored hierarchically to reflect the nature of many processors to have complex operands. Typically, each operand is assigned an extension. For further clean-up, extensions may be nested, so the full description structure of an operation is a tree.

Extensions are stored in the attribute 'ext', which is a vector, each element representing one extension.

Each extension in the vector can have attributes just like any other item in CRL2, therefore, it is implemented as a map from Symbol keys to arbitrary CRL2 Values. Thus, the vector of extension contains Maps as elements.

In the following, attributes will be listed for every item. Those attributes that can occur at operations as well as in extensions will be listed in a seperate section.

Generic Attributes

These are used across architectures and analyses and these are present directly after decoding, i.e., exec2crl produces them.

Operation & Extension

These attributes may be found at operations and in extensions. Thus they constitute the hierarchical information stored at operations.

Operation

Instruction

Block

Routine

routine X is not analysed

routine X is external

Global

These attributes are found at the graph.

Data & Bytes & Info & Meta

Yet to be documented.

AbsInt aiT/StackAnalyzer Attributes

Block

Routine

Global

These attributes are found at the graph.

AbsInt aiT/StackAnalyzer User Attributes

Operation

instruction X accesses Y

instruction X accesses Y in step Z

instruction X accesses Y speculatively

instruction X accesses Y in step Z speculatively

instruction X is entered with r1=Y, r2=Z, ...;

user_* Value User defined additional attributes. The AIS names get a 'user_' prefix when moved into the CRL2 structure. | AIS: : instruction X features KEY=VAL, KEY=VAL, ...; +-------------------------+-----------+-----------------------------------------------------------+

Block

loop X iterates Y;

instruction X additionally takes Y;

Routine

loop X iterates Y

routine X is not analysed and takes Y

read default X from Y

write default X to Y

read restrict X to Y

write restrict X to Y

loop iteration default X is Y

loop iteration restrict X is Y

routine X incarnates Y

routine X uses Y bytes of stack

routine X leaves behind Y bytes of stack

routine X violates calling conventions

routine X features KEY=VAL, KEY=VAL, ...;

Global

These attributes are found at the graph.

clock X

global read default from Y

global write default to Y

global read restrict to Y

global write restrict to Y

global loop iteration default is Y

global loop iteration default is Y

flow X / Y is Z

Flow

A flow relations is currently a relation of linear combination of program points, i.e., a sum of program point counts and constant coefficients, compared with =, <= or >=.

The linear combinations are simple represented as a vector. Each element is an Application with type INFIX and functor '*'. The relations are represented by an infix Application with one of the functors '>=', '<=' or '='.

If the relation holds for each context, not only for the sum over all contexts, then another prefix Application with the functor 'each' is applied.

These relations are arranged in a vector and are found in this form in the global 'flow_relations' attribute.

Here's an example:

CRL2:

 [
    ([ i8 ] '>=' [ ([ 5 ]   '*' [ i10 ]) ]),
    ([ i8 ] '<=' [ ([ 0xa ] '*' [ i10 ]) ]),
    ('each'[
        ([ i354 ] '>=' [ ([ 6 ] '*' [ i356 ]) ])
    ]),
    ('each'[
        ([ i354 ] '<=' [ ([ 0x16 ] '*' [ i356 ]) ])
    ])
 ]

PAG

FIXME: add more docu.

Here's an example:

CRL2:

mapping="VIVU-4,len=inf,def_unroll=2"

Cache

(Copied from the internal document exec2crl/doc/spec_format.txt)

lows setting the cache parameters for different levels of a cache. Each level may distinguish instruction, data and unified cache.

An example in AIS looks as follows:

cache
   first level data
       set-count = 128, associativity = 4, line-size = 16
and second level data
        size = 262144, associativity = 8, line-size = 32;

The general syntax is:

'cache'
Cache specifitation (non-empty, 'and'-separated list): :    (
Cache Level (optional): :        (
          ('first' | 'second' | 'third' | 'fourth' | 'fifth' ) 'level'
       |  'level' INT
       )?
If this is missing, 'first level' is assumed. :
Cache Scope (optional): :        ( 'data' | 'instruction' | 'unified' )?
If this is missing, 'unified is assumed. :
Feature List (non-empty, comma separated list): :        ( 'set-count'     '=' INT
       | 'associativity' '=' INT
       | 'line-size'     '=' INT
       | 'line-count'    '=' INT
       | 'size'          '=' INT
       | 'policy'        '=' ( 'plruppc' | 'lru' )
       | 'may'           '=' ( 'none' | 'empty' | 'chaos' )
       | 'pers'          '=' ( 'none' | 'empty' | 'chaos' )
       | 'must'          '=' ( 'true' | 'false' )
       )','+
   )'and'+

The cache geometry must be specified by an arbitrary selection of the parameters 'set-count', 'associativity', 'line-size', 'line-count' and 'size' in such a way that the other parameters can be inferred.

From this specification, exec2crl generates a set of global attributes. The keys of the attributes have one of the following forms:

If the level is not given:

<SCOPE>cache_<FEATURE>

If the level is given:

level<LEVEL><SCOPE>cache<FEATURE>

Here, SCOPE may be:

FEATURE may be:

Example attribute:

CRL2:

cache=[
     { // level 1
         data={
             associativity=4,
             line_size=0x100,
             size=0x20000
             policy='lru',
             must='empty',
             may='none',
             pers='none',
         }
         instruction={
             ...
         }
         unified={
             ...
         }
     },
     { // level 2
         data={
             ...
         }
         ...
     }
     ...
]

Note that all attributes may be missing if they are not specified. Also note that there is no default for the level: instead, there are different attributes for the case where no level was specified. Maybe this should be changed and the default should be level 1.

You should decide yourself when to issue error messages and tell the behaviour to the master of documentation.

The attributes 'size', 'line_size' and 'associativity' are always specified together, i.e., either exec2crl specifies all, or none of them.