This module allows to represents program as a Control Flow Graph (CFG). The CFG is graph representation of the execution path of the program where nodes represents either a basic block, or a synthetic blocks, and edges, Edge, the control flow transitions between blocks. A BasicBlock, represents blocks of sequential instructions. A synthetic block represents sub-CFG references a CFG that may be a subprogram call or a separated subgraph of blocks. Whatever, CFG have usually a single entry point and a single exit point. Only subprograms with unresolved control target supports a second exit node, called "unknown": unresolved branches are implemented as edges from the current basic block to the unknown node. More...

Classes
class	otawa::AbstractCFGBuilder

class	otawa::BasicBlock

class	otawa::Block

class	otawa::CFG

class	otawa::CFGBuilder

class	otawa::CFGChecker

class	otawa::CFGCheckSummer

class	otawa::CFGCollection

class	otawa::CFGCollector

class	otawa::CFGInfo

class	otawa::CFGMaker

class	otawa::CFGNormalizer

class	otawa::CFGTransformer

class	otawa::DelayedBuilder

class	otawa::DomInfo

class	otawa::Edge

class	otawa::Loop

class	otawa::LoopManager

class	otawa::LoopReductor

class	otawa::LoopUnroller

class	otawa::PhonyBlock

class	otawa::PostDomInfo

class	otawa::ip::Predecessor

class	otawa::ip::Successor

class	otawa::SynthBlock

Functions
p::id< Address >	otawa::ADDED_CFG ("otawa::ADDED_CFG", 0)
	This configuration property allows to add unlinked CFG to the used CFG collection. More...

p::id< CString >	otawa::ADDED_FUNCTION ("otawa::ADDED_FUNCTION", 0)
	This configuration property allows to add unlinked functions to the used CFG collection. More...

Identifier< bool >	otawa::BACK_EDGE ("otawa::BACK_EDGE", false)
	Identifier for marking back edges. More...

p::id< Bag< Address > >	otawa::BB_BOUNDS ("otawa::BB_BOUNDS")
	Configuration identifier, provides a list of BB start point (whatever the control flow of the executable). More...

p::id< Edge * >	otawa::CALLED_BY ("otawa::CALLED_BY", 0)
	This properties are put on a CFG to get the list of edges calling it. More...

p::feature	otawa::CFG_CHECKSUM_FEATURE ("otawa::CFG_CHECKSUM_FEATURE", new Maker< CFGCheckSummer >())
	This feature ensures that each CFG has hooked a checksum allowing to check binary modifications between launch of an OTAWA application. More...

Identifier< const CFGInfo * >	otawa::CFG_INFO ("otawa::CFG_INFO", 0)
	Get the collection of CFG found in the program. More...

p::feature	otawa::CFG_INFO_FEATURE ("otawa::CFG_INFO_FEATURE", new Maker< CFGBuilder >())
	Feature asserting that the CFG has been scanned in the program. More...

p::id< Address >	otawa::CFG_START ("otawa::CFG_START")
	Provide the start address of a sub-CFG to extract (inclusive). More...

p::id< Address >	otawa::CFG_STOP ("otawa::CFG_STOP", false)
	Provide the stop address of a sub-CFG to extract (exclusive). More...

p::feature	otawa::CHECKED_CFG_FEATURE ("otawa::CHECKED_CFG_FEATURE", new Maker< CFGChecker >())
	This feature ensures that. More...

Identifier< unsigned long >	otawa::CHECKSUM ("otawa::CHECKSUM", 0)
	This property hooked on a CFG provides a checksum build on the instruction of the CFG. More...

p::interfaced_feature< const CFGCollection >	otawa::COLLECTED_CFG_FEATURE ("otawa::COLLECTED_CFG_FEATURE", new Maker< CFGCollector >())
	This feature asserts that all CFG involved in the current computation has been collected and accessible thanks to INVOLVED_CFGS property. More...

p::feature	otawa::DELAYED_CFG_FEATURE ("otawa::DELAYED_CFG_FEATURE", new Maker< DelayedBuilder >())
	This feature informs that the current microprocessor supports delayed branches and that the CFG has been changed to reflect effect of delay branches. More...

Identifier< bool >	otawa::DELAYED_INST ("otawa::DELAYED_INST", false)
	This property is set on instruction of a delayed branch. More...

Identifier< bool >	otawa::DELAYED_NOP ("otawa::DELAYED_NOP", false)
	This property is true on NOP instructions insserted due to branch delay. More...

p::interfaced_feature< DomInfo >	otawa::DOMINANCE_FEATURE ("otawa::DOMINANCE_FEATURE", new Maker< Dominance >())
	This feature ensures that information about domination between nodes of a CFG is available. More...

p::id< CFG * >	otawa::ENTRY_CFG ("otawa::entry_cfg", 0)
	This property is used to get the entry CFG of the currently processed task. More...

p::id< elm::Vector< Edge * > * >	otawa::EXIT_LIST ("otawa::EXIT_LIST", 0)
	Defined for any BasicBlock that is a loop header. More...

Identifier< bool >	otawa::INLINING_POLICY ("otawa::INLINING_POLICY")
	Put on the first instruction of a function to set default inlining behavior during its virtualization. More...

p::id< const CFGCollection * >	otawa::INVOLVED_CFGS ("otawa::INVOLVED_CFGS", 0)
	This property is used to link the current computation involved CFG on the framework. More...

p::id< location_t >	otawa::LOCATION_START ("otawa::LOCATION_START", location_t(nullptr, nullptr))
	Provide the start location of a sub-CFG to extract (inclusive). More...

p::id< location_t >	otawa::LOCATION_STOP ("otawa::LOCATION_STOP", location_t(nullptr, nullptr))
	Provide the stop location of a sub-CFG to extract (inclusive). More...

p::id< Block * >	otawa::LOOP_ENTRY ("otawa::LOOP_ENTRY", nullptr)
	Is defined for an Edge if this Edge is the entry-edge of any loop. More...

p::id< Block * >	otawa::LOOP_EXIT ("otawa::LOOP_EXIT", nullptr)
	Is defined for an Edge if this Edge is the exit-edge of any loop. More...

Identifier< bool >	otawa::LOOP_HEADER ("otawa::LOOP_HEADER", false)
	Identifier for marking basic blocks that are entries of loops. More...

Identifier< bool >	otawa::NO_INLINE ("otawa::NO_INLINE")
	Put on the first instruction of a function to indicate whether it should be inlined or not during virtualization. More...

	otawa::PostDominance::PostDominance (p::declare &r=reg)
	The postdominance processors computes postdominance relation on the current CFG. More...

p::interfaced_feature< PostDomInfo >	otawa::POSTDOMINANCE_FEATURE ("otawa::POSTDOMINANCE_FEATURE", new Maker< PostDominance >())
	This feature ensures that information about postdomination between nodes of a CFG is vailable. More...

p::feature	otawa::SPLIT_CFG ("otawa::SPLIT_CFG", p::make< SubCFGBuilder >())
	This feature ensure that a part of the current has been extracted as a sub-CFG based on address provided by two properties: More...

Identifier< Block * >	otawa::UNROLLED_FROM ("otawa::UNROLLED_FROM", 0)
	Put on the header ex-header of a loop, this property gives the BB of the unrolled loop. More...

p::feature	otawa::UNROLLED_LOOPS_FEATURE ("otawa::UNROLLED_LOOPS_FEATURE", new Maker< LoopUnroller >())
	This feature that the loops have been unrolled at least once. More...

Variables
p::id< Address >	otawa::ADDED_CFG
	This configuration property allows to add unlinked CFG to the used CFG collection. More...

p::id< CString >	otawa::ADDED_FUNCTION
	This configuration property allows to add unlinked functions to the used CFG collection. More...

Identifier< bool >	otawa::BACK_EDGE
	Identifier for marking back edges. More...

p::id< Bag< Address > >	otawa::BB_BOUNDS
	Configuration identifier, provides a list of BB start point (whatever the control flow of the executable). More...

p::id< Edge * >	otawa::CALLED_BY
	This properties are put on a CFG to get the list of edges calling it. More...

p::feature	otawa::CFG_CHECKSUM_FEATURE
	This feature ensures that each CFG has hooked a checksum allowing to check binary modifications between launch of an OTAWA application. More...

Identifier< const CFGInfo * >	otawa::CFG_INFO
	Get the collection of CFG found in the program. More...

p::feature	otawa::CFG_INFO_FEATURE
	Feature asserting that the CFG has been scanned in the program. More...

p::id< Address >	otawa::CFG_START
	Provide the start address of a sub-CFG to extract (inclusive). More...

p::id< Address >	otawa::CFG_STOP
	Provide the stop address of a sub-CFG to extract (exclusive). More...

p::feature	otawa::CHECKED_CFG_FEATURE
	This feature ensures that. More...

Identifier< unsigned long >	otawa::CHECKSUM
	This property hooked on a CFG provides a checksum build on the instruction of the CFG. More...

p::interfaced_feature< const CFGCollection >	otawa::COLLECTED_CFG_FEATURE
	This feature asserts that all CFG involved in the current computation has been collected and accessible thanks to INVOLVED_CFGS property. More...

p::feature	otawa::DELAYED_CFG_FEATURE
	This feature informs that the current microprocessor supports delayed branches and that the CFG has been changed to reflect effect of delay branches. More...

Identifier< bool >	otawa::DELAYED_INST
	This property is set on instruction of a delayed branch. More...

Identifier< bool >	otawa::DELAYED_NOP
	This property is true on NOP instructions insserted due to branch delay. More...

p::interfaced_feature< DomInfo >	otawa::DOMINANCE_FEATURE
	This feature ensures that information about domination between nodes of a CFG is available. More...

p::id< CFG * >	otawa::ENTRY_CFG
	This property is used to get the entry CFG of the currently processed task. More...

p::id< elm::Vector< Edge * > * >	otawa::EXIT_LIST
	Defined for any BasicBlock that is a loop header. More...

static Identifier< const CFGInfo * > &	otawa::CFGInfo::ID = CFG_INFO
	This property allows to get the CFG information from the current CFG is member of. More...

Identifier< bool >	otawa::INLINING_POLICY
	Put on the first instruction of a function to set default inlining behavior during its virtualization. More...

p::id< const CFGCollection * >	otawa::INVOLVED_CFGS
	This property is used to link the current computation involved CFG on the framework. More...

p::id< location_t >	otawa::LOCATION_START
	Provide the start location of a sub-CFG to extract (inclusive). More...

p::id< location_t >	otawa::LOCATION_STOP
	Provide the stop location of a sub-CFG to extract (inclusive). More...

p::id< Block * >	otawa::LOOP_ENTRY
	Is defined for an Edge if this Edge is the entry-edge of any loop. More...

p::id< Block * >	otawa::LOOP_EXIT
	Is defined for an Edge if this Edge is the exit-edge of any loop. More...

p::id< Block * > &	otawa::LOOP_EXIT_EDGE = LOOP_EXIT

Identifier< bool >	otawa::LOOP_HEADER
	Identifier for marking basic blocks that are entries of loops. More...

static Identifier< bool >	otawa::CFGChecker::NO_EXCEPTION
	In configuration of otawa::CFGChecker . More...

Identifier< bool >	otawa::NO_INLINE
	Put on the first instruction of a function to indicate whether it should be inlined or not during virtualization. More...

p::interfaced_feature< PostDomInfo >	otawa::POSTDOMINANCE_FEATURE
	This feature ensures that information about postdomination between nodes of a CFG is vailable. More...

p::feature	otawa::SPLIT_CFG
	This feature ensure that a part of the current has been extracted as a sub-CFG based on address provided by two properties: More...

Identifier< Block * >	otawa::UNROLLED_FROM
	Put on the header ex-header of a loop, this property gives the BB of the unrolled loop. More...

p::feature	otawa::UNROLLED_LOOPS_FEATURE
	This feature that the loops have been unrolled at least once. More...

Detailed Description

This module allows to represents program as a Control Flow Graph (CFG). The CFG is graph representation of the execution path of the program where nodes represents either a basic block, or a synthetic blocks, and edges, Edge, the control flow transitions between blocks. A BasicBlock, represents blocks of sequential instructions. A synthetic block represents sub-CFG references a CFG that may be a subprogram call or a separated subgraph of blocks. Whatever, CFG have usually a single entry point and a single exit point. Only subprograms with unresolved control target supports a second exit node, called "unknown": unresolved branches are implemented as edges from the current basic block to the unknown node.

Using the CFG

Most analyses only read the CFG structure and either use the properties of the CFG, or creates new properties. They only need to understand the structure of the CFG.

Most classes, features and identifier are accessible in the header file:

#include <otawa/cfg/features.h>

A CFG is made mainly of 5 classes:

CFG – the CFG itself providing entry and exit virtual nodes and the list of BB,
Edge – an edge in the CFG linking a source BB with a target BB,
Block – a block with a list of input edges and list of output edges,
BasicBlock – subclass of Block, sequence of instructions with address and size,
SynthBlock – subclass of Block, sub-CFG, potentially a subprogram.

These classes are subclasses of PropList and therefore support properties.

To visit a CFG, one has to start from either the entry, or the exit block (that are not virtual blocks and does not match any code in the program) and follows the edges (be aware that a CFG may contain loops !). To get the outputting edges of a BB, the following code based on the iterator BasicBlock::OutIterator may apply:

for(BasicBlock::OutIter edge = bb->outs(); edge; edge++)

process(edge);

Another way to work CFG is to make the analysis class to inherit from one of the following standard processors:

CFGProcessor – call method CFGProcessor::processCFG() for each CFG in the task,
BBProcessor – call method BBProcessor::processBB() for each BB of the CFGs of the task,
EdgeProcessor – call method EdgeProcessor::processEdge() for each edge of the CFGs of the task.

They will avoid the hassle work of traversing the different CFGs of the task and BB and edges inside the CFGs.

As an example, the following analysis outputs the CFG and disassemble the instructions in the BB.

class Disassembler: public BBProcessor {
protected:
        virtual void processCFG(WorkSpace *ws, CFG *cfg) {
                cout << "CFG " << cfg->label() << io::endl;
                BBProcessor::processCFG(ws, cfg);
        }
 
        virtual void processBB(WorkSpace *ws, CFG *cfg, BasicBlock *bb) {
                if(bb->isVirtual())
                        return;
        cout << "\t" << bb << io::endl;
        for(BasicBlock::InstIter inst = bb->insts(); inst; inst++)
                cout << "\t\t" << inst->address() << "\t" << *inst << io::endl;
        }
};

One may also observe that the CFG representation fully supports transformations like inlining of called sub-program or the representation of a possible exception raise. As shown in the section on the transformation of CFG, these transformations does not duplicate code or changes the original program. Only the representation is modified and aims at improving the precision in some particular cases.

Finally, a CFG may be called at different points in the other CFGs of the program, the properties CALLED_BY hooked to the CFG allows to get the matching calling edges:

for(Identifier<Edge *>::Getter edge(cfg, CALLED_BY); edge; edge++)

processCaller(cfg, edge);

Building the CFGs

Once a program is loaded, OTAWA has only two information item on the structure of the program: the block of bytes representing the program and the startup address of the program. In addition, according to the option of linkage, other symbols may be available like the entry points of the functions composing the program.

From this, OTAWA must decode the instructions from these entry points and follows all execution paths until fully decoding the program. This first phase is performed the CFGBuilder analysis that produces as an output, a CFGInfo, the collection of all CFGs (one by function) of the program. This phase is relatively complex and may fail because of:

errors in decoding the instructions (in this case, the error is signaled to the user and the execution path is aborted),
unresolved branches (mainly because of computed branch target as found in function pointer call or in some switch compilation schemes).

For the latter case, you can help CFGBuilder by providing information on the possible branches using the properties below:

IS_RETURN – consider the marked instruction as a return,
NO_RETURN – mark the function as not returning,
NO_CALL – avoid to involve in the CFGs the function whose first instruction is marked,
IGNORE_CONTROL – ignore the control effect of the marked instruction,
IGNORE_SEQ – only on a conditional branching instruction, ignore the sequential path,
BRANCH_TARGET – gives the target(s) of an indirect branch instruction,
CALL_TARGET – gives the target(s) of an indirect call instruction.

This properties are usually set by the FlowFactLoader from textual or XML files. Once may also observe that this properties allows also to change artificially the control flow according to the needs of a user. For example, one can avoid the "printf" function to be called by putting a property NO_CALL on its entry instruction.

Once the global CFGs of the program are built, the user is usually interested only in a subset of CFGS corresponding to the task the WCET is computed for. This subset is gathered by the CFGCollector analysis from one of the following properties:

TASK_ENTRY (in the configuration properties)
ENTRY_CFG (in the configuration properties or on the workspace)
CFGCollector::ADDED_CFG – CFG to add to the collection,
CFGCollection::ADD_FUNCTION – function to add to the collection.

As a result, the INVOLVED_CFGS (type CFGCollection) hooked to the workspace provides this list of functions that is used by the following analyses to perform the WCET computation. Notices that the first CFG of the collection is the entry point of the task. Remark also that the obtained CFG are a copy of the original CFG of the global decoding of the program: this means that you add as many properties to the collected CFG without impacting the CFGs of the global analysis.

Loops in the CFGs

Loops are a common shared issue when handling CFG. OTAWA provides several way to cope with loops. First two features allows to identify loops: LOOP_HEADERS_FEATURE and LOOP_INFO_FEATURE.

The LOOP_HEADERS_FEATURE allows to identify the loops in the CFG. Basically, it finds the back-edges (edges causing the looping) and, from these, the header of the loops. Each loop is defined by its header basic block that is the first basic block traversed when entering a loop. An header basic block is the header of only one loop and is a good way to identify the loop. The following properties are set:

LOOP_HEADER – evaluates to true when the hooked basic block is a loop header,
BACK_EDGE – evaluates to true on a back-edge (the target of the edge is the loop header).

This feature is implemented by the Dominance analysis or SpanningTreeBuilder.

If LOOP_HEADERS_FEATURE provides minimal information on a loop, LOOP_INFO_FEATURE allows to get full details sometimes for some analyses. The following properties are set:

ENCLOSING_LOOP_HEADER – gives the header of the loop enclosing the linked BB,
LOOP_EXIT_EDGE – on an edge, informs it is an exit edgen,
EXIT_LIST – put on the loop header, get the list of edges exiting the loop.

As shown above, the loop handled by OTAWA supports only one entry point and header. This is a classic definition of so-called "regular" loops. Even if this is the most common loop found, some programs exhibit "irregular" loops (at least, two possible entry point). A usual way to support such a loop is to choose one entry point and to duplicate the code of the other entry points: this may be done in OTAWA using the analysis LoopReductor.

Transforming the CFG

CFGs in OTAWA are designed to be light representation of the program, that is, they support duplication with a minimal cost in term of memory footprint. This means, for example, that the precision of the computed WCET may be improved by duplicating some parts of the CFG to cope more precisely with the context of the code. Several OTAWA code processors provide such transformations.

The Virtualizer allows to inline the called function at the location they are called. Therefore, if a function is called at several locations, this allows to duplicate the BB and the edges representing the function and, instead to melt the context information, to have a context as precise as possible. Yet, such a transformation may be costly in terms of number of BB and must be used carefully. To prevent such a size explosion, you can mark a CFG as DONT_INLINE to prevent the inlining.

Unrolling loops is another way to improve precision. As many loop body have a different behavior between the first iteration and the other one (cache load, etc), it may be interesting to unroll loops once. This may be performed using the code processor LoopUnroller.

Finally, some transformations are required by a particular architecture. This is the case of instruction sets with delayed branches. Delayed branches executes the instruction following the branch instruction before performing actually the control flow change. As an outcome, the instruction following a branch is really part of the basic block the branch is contained in. This policy is different from the usual way OTAWA builds CFGs and a transformation must be done to fix the basic blocks: this is performed by DelayedBuilder.

Input / Output in XML

This modules provides two code processors allowing to perform input / output on CFG. CFGSaver save the CFG of the current task to a file while CFGLoader allows to load it back.

Both processors uses the same XML format defined below:

<?xml version="1.0" ?>
<otawa-workspace>
 
                <cfg id="ID" entry="ID" exit="ID">
                        <bb id="ID" address="ADDRESS"? size="INT"?/>*
                        <edge kind="KIND" source="ID" target="ID"? cfg="ID"?/>*
        </cfg>*
 
</otawa-workspace>

The OTAWA workspace is viewed, in the CFG representation, as a set of CFG that, in turn, is made of several basic blocks linked by edges. Each CFG and BB is identified with the attribute "id", any textual unique value, allowing to reference them.

The cfg element must reference two specific BB (using the unique "id"), an entry BB and an exit BB. The BB is defined by its address and its size (in bytes). The edges are defined by their kind, the source BB and, depending on the type, the target BB or the called CFG (Edge::CALL). The latter attribute "cfg" must give the identifier of an existing CFG.

Function Documentation

◆ ADDED_CFG()

p::id<Address> otawa::ADDED_CFG	(	"otawa::ADDED_CFG"	,
		0
	)

This configuration property allows to add unlinked CFG to the used CFG collection.

◆ ADDED_FUNCTION()

p::id<CString> otawa::ADDED_FUNCTION	(	"otawa::ADDED_FUNCTION"	,
		0
	)

This configuration property allows to add unlinked functions to the used CFG collection.

◆ BACK_EDGE()

Identifier<bool> otawa::BACK_EDGE	(	"otawa::BACK_EDGE"	,
		false
	)

Identifier for marking back edges.

Hooks

BasicBlock

◆ BB_BOUNDS()

p::id<Bag<Address> > otawa::BB_BOUNDS ( "otawa::BB_BOUNDS" )

Configuration identifier, provides a list of BB start point (whatever the control flow of the executable).

◆ CALLED_BY()

p::id<Edge *> otawa::CALLED_BY	(	"otawa::CALLED_BY"	,
		0
	)

This properties are put on a CFG to get the list of edges calling it.

Hooks

CFG

◆ CFG_CHECKSUM_FEATURE()

p::feature otawa::CFG_CHECKSUM_FEATURE	(	"otawa::CFG_CHECKSUM_FEATURE"	,
		new Maker< CFGCheckSummer >	()
	)

This feature ensures that each CFG has hooked a checksum allowing to check binary modifications between launch of an OTAWA application.

Properties

CHECKSUM

◆ CFG_INFO()

Identifier<const CFGInfo *> otawa::CFG_INFO	(	"otawa::CFG_INFO"	,
		0
	)

Get the collection of CFG found in the program.

Feature

CFG_INFO_FEATURE

Hooks: WorkSpace

◆ CFG_INFO_FEATURE()

p::feature otawa::CFG_INFO_FEATURE	(	"otawa::CFG_INFO_FEATURE"	,
		new Maker< CFGBuilder >	()
	)

Feature asserting that the CFG has been scanned in the program.

The result is put the CFGInfo::ID.

@Properties

CFG_INFO

◆ CFG_START()

p::id<Address> otawa::CFG_START ( "otawa::CFG_START" )

Provide the start address of a sub-CFG to extract (inclusive).

Only one start address can be given. If not provided, the start is assumed to be the first address of the CFG.

Feature

otawa::SPLIT_CFG

◆ CFG_STOP()

p::id<Address> otawa::CFG_STOP	(	"otawa::CFG_STOP"	,
		false
	)

Provide the stop address of a sub-CFG to extract (exclusive).

Several stop address can be given. If not provided, the stop is assumed to be the last address of the blocks preceding the exit of the current CFG.

Feature

otawa::SPLIT_CFG

◆ CHECKED_CFG_FEATURE()

p::feature otawa::CHECKED_CFG_FEATURE	(	"otawa::CHECKED_CFG_FEATURE"	,
		new Maker< CFGChecker >	()
	)

This feature ensures that.

there exists at least one path from the entry to the exit,
no branch is unresolved.

Default Processor

CFGChecker

◆ CHECKSUM()

Identifier<unsigned long > otawa::CHECKSUM	(	"otawa::CHECKSUM"	,
		0
	)

This property hooked on a CFG provides a checksum build on the instruction of the CFG.

◆ COLLECTED_CFG_FEATURE()

p::interfaced_feature<const CFGCollection> otawa::COLLECTED_CFG_FEATURE	(	"otawa::COLLECTED_CFG_FEATURE"	,
		new Maker< CFGCollector >	()
	)

This feature asserts that all CFG involved in the current computation has been collected and accessible thanks to INVOLVED_CFGS property.

Configuration

Properties

ENTRY_CFG (WorkSpace).
INVOLVED_CFGS (WorkSpace).

◆ DELAYED_CFG_FEATURE()

p::feature otawa::DELAYED_CFG_FEATURE	(	"otawa::DELAYED_CFG_FEATURE"	,
		new Maker< DelayedBuilder >	()
	)

This feature informs that the current microprocessor supports delayed branches and that the CFG has been changed to reflect effect of delay branches.

Default Processor

otawa::DelayedBuilder

Properties

◆ DELAYED_INST()

Identifier<bool> otawa::DELAYED_INST	(	"otawa::DELAYED_INST"	,
		false
	)

This property is set on instruction of a delayed branch.

Features

otawa::DELAYED_CFG_FEATURE

Hooks

otawa::Inst

◆ DELAYED_NOP()

Identifier<bool> otawa::DELAYED_NOP	(	"otawa::DELAYED_NOP"	,
		false
	)

This property is true on NOP instructions insserted due to branch delay.

Features

otawa::DELAYED_CFG_FEATURE

Hooks

otawa::Inst

◆ DOMINANCE_FEATURE()

p::interfaced_feature<DomInfo> otawa::DOMINANCE_FEATURE	(	"otawa::DOMINANCE_FEATURE"	,
		new Maker< Dominance >	()
	)

This feature ensures that information about domination between nodes of a CFG is available.

Back edges are marked with BACK_EDGE property while dominance may be tested using an interface of type DomInfo and provided by DOM_INFO property.

OTAWA provides several implementation of domination calculation:

otawa::Dominance

Properties

BACK_EDGE
DOM_INFO

◆ ENTRY_CFG()

p::id<CFG *> otawa::ENTRY_CFG	(	"otawa::entry_cfg"	,
		0
	)

This property is used to get the entry CFG of the currently processed task.

@para Hooks

WorkSpace

◆ EXIT_LIST()

p::id<elm::Vector<Edge > > otawa::EXIT_LIST	(	"otawa::EXIT_LIST"	,
		0
	)

Defined for any BasicBlock that is a loop header.

Contain a list of the exit edges associated with the loop (more clearly, EXIT_LIST(h) is the list of the edges for which LOOP_EXIT_EDGE(edge) == h)

Hooks

BasicBlock

◆ INLINING_POLICY()

Identifier<bool> otawa::INLINING_POLICY ( "otawa::INLINING_POLICY" )

Put on the first instruction of a function to set default inlining behavior during its virtualization.

This overrides VIRTUAL_INLINING default policy of Virtualizer.

FLOW_FACTS_FEATURE
Hooks
Inst

◆ INVOLVED_CFGS()

p::id<const CFGCollection *> otawa::INVOLVED_CFGS	(	"otawa::INVOLVED_CFGS"	,
		0
	)

This property is used to link the current computation involved CFG on the framework.

Hooks

WorkSpace

◆ LOCATION_START()

p::id<location_t> otawa::LOCATION_START	(	"otawa::LOCATION_START"	,
		location_t(nullptr, nullptr)
	)

Provide the start location of a sub-CFG to extract (inclusive).

Only one start location can be given. If not provided, the start location is assumed to be the first address of the CFG.

Feature

otawa::SPLIT_CFG

◆ LOCATION_STOP()

p::id<location_t> otawa::LOCATION_STOP	(	"otawa::LOCATION_STOP"	,
		location_t(nullptr, nullptr)
	)

Provide the stop location of a sub-CFG to extract (inclusive).

Several stop locations can be given. If not provided, the stop location is assumed to be the last instruction of the blocks preceding the exit of the current CFG.

Feature

otawa::SPLIT_CFG

◆ LOOP_ENTRY()

p::id<Block*> otawa::LOOP_ENTRY	(	"otawa::LOOP_ENTRY"	,
		nullptr
	)

Is defined for an Edge if this Edge is the entry-edge of any loop.

If this is the case, then, the property contains the header of the loop exited by the edge.

Hooks

Edge

◆ LOOP_EXIT()

p::id<Block*> otawa::LOOP_EXIT	(	"otawa::LOOP_EXIT"	,
		nullptr
	)

Is defined for an Edge if this Edge is the exit-edge of any loop.

If this is the case, then, the property contains the header of the loop exited by the edge. If the edge exits more than one loop, the property contains the header of the outer loop.

Hooks

Edge

◆ LOOP_HEADER()

Identifier<bool> otawa::LOOP_HEADER	(	"otawa::LOOP_HEADER"	,
		false
	)

Identifier for marking basic blocks that are entries of loops.

Hooks

BasicBlock

◆ NO_INLINE()

Identifier<bool> otawa::NO_INLINE ( "otawa::NO_INLINE" )

Put on the first instruction of a function to indicate whether it should be inlined or not during virtualization.

This overrides VIRTUAL_INLINING default policy of Virtualizer and INLINING_POLICY of the caller CFG.

FLOW_FACTS_FEATURE
Hooks
Inst

◆ PostDominance()

otawa::PostDominance::PostDominance ( p::declare & r = reg )

The postdominance processors computes postdominance relation on the current CFG.

Provided Features

PDOM_INFO

Required Features

COLLECTED_CFG_FEATURE

◆ POSTDOMINANCE_FEATURE()

p::interfaced_feature<PostDomInfo> otawa::POSTDOMINANCE_FEATURE	(	"otawa::POSTDOMINANCE_FEATURE"	,
		new Maker< PostDominance >	()
	)

This feature ensures that information about postdomination between nodes of a CFG is vailable.

Properties

REVERSE_DOM (BasicBlock)

◆ SPLIT_CFG()

p::feature otawa::SPLIT_CFG	(	"otawa::SPLIT_CFG"	,
		p::make< SubCFGBuilder >	()
	)

This feature ensure that a part of the current has been extracted as a sub-CFG based on address provided by two properties:

otawa::CFG_START (only one allowed)
otawa::CFG_STOP (several allowed)

This addresses must match instructions of the task entry function and all basic blocks on the paths from start addresses to stop addresses are included in the sub-CFG.

Configuration

Only one otawa::CFG_START or otawa::LOCATION_START can be defined.

Default processor

otawa::SubCFGBuilder

◆ UNROLLED_FROM()

Identifier<Block *> otawa::UNROLLED_FROM	(	"otawa::UNROLLED_FROM"	,
		0
	)

Put on the header ex-header of a loop, this property gives the BB of the unrolled loop.

Hooks

BasicBlock

◆ UNROLLED_LOOPS_FEATURE()

p::feature otawa::UNROLLED_LOOPS_FEATURE	(	"otawa::UNROLLED_LOOPS_FEATURE"	,
		new Maker< LoopUnroller >	()
	)

This feature that the loops have been unrolled at least once.

Configuration

UNROLL_THIS – mark loops to unroll

Properties

UNROLLED_FROM

Variable Documentation

◆ ADDED_CFG

p::id<Address> otawa::ADDED_CFG("otawa::ADDED_CFG", 0)

This configuration property allows to add unlinked CFG to the used CFG collection.

◆ ADDED_FUNCTION

p::id<CString> otawa::ADDED_FUNCTION("otawa::ADDED_FUNCTION", 0)

This configuration property allows to add unlinked functions to the used CFG collection.

◆ BACK_EDGE

Identifier< bool > otawa::BACK_EDGE

Identifier for marking back edges.

Hooks

BasicBlock

Referenced by otawa::ai::PseudoTopoOrder::_getPseudoTopo(), otawa::ai::PseudoTopoOrder::_topoNodeHelper(), otawa::Loop::isBack(), otawa::ai::FlowAwareRanking::processWorkSpace(), otawa::BackIter::step(), and otawa::EntryIter::step().

◆ BB_BOUNDS

p::id<Bag<Address> > otawa::BB_BOUNDS("otawa::BB_BOUNDS")

Configuration identifier, provides a list of BB start point (whatever the control flow of the executable).

Referenced by otawa::AbstractCFGBuilder::configure().

◆ CALLED_BY

p::id<Edge *> otawa::CALLED_BY("otawa::CALLED_BY", 0)

This properties are put on a CFG to get the list of edges calling it.

Hooks

CFG

◆ CFG_CHECKSUM_FEATURE

p::feature otawa::CFG_CHECKSUM_FEATURE("otawa::CFG_CHECKSUM_FEATURE", new Maker< CFGCheckSummer >())

This feature ensures that each CFG has hooked a checksum allowing to check binary modifications between launch of an OTAWA application.

Properties

CHECKSUM

Referenced by otawa::CFGCheckSummer::CFGCheckSummer().

◆ CFG_INFO

Identifier<const CFGInfo *> otawa::CFG_INFO("otawa::CFG_INFO", 0)

Get the collection of CFG found in the program.

Feature

CFG_INFO_FEATURE

Hooks: WorkSpace

◆ CFG_INFO_FEATURE

p::feature otawa::CFG_INFO_FEATURE("otawa::CFG_INFO_FEATURE", new Maker< CFGBuilder >())

Feature asserting that the CFG has been scanned in the program.

The result is put the CFGInfo::ID.

@Properties

CFG_INFO

◆ CFG_START

p::id< Address > otawa::CFG_START

Provide the start address of a sub-CFG to extract (inclusive).

Only one start address can be given. If not provided, the start is assumed to be the first address of the CFG.

Feature

otawa::SPLIT_CFG

Referenced by otawa::SubCFGBuilder::configure().

◆ CFG_STOP

p::id< Address > otawa::CFG_STOP

Provide the stop address of a sub-CFG to extract (exclusive).

Several stop address can be given. If not provided, the stop is assumed to be the last address of the blocks preceding the exit of the current CFG.

Feature

otawa::SPLIT_CFG

Referenced by otawa::SubCFGBuilder::configure().

◆ CHECKED_CFG_FEATURE

p::feature otawa::CHECKED_CFG_FEATURE("otawa::CHECKED_CFG_FEATURE", new Maker< CFGChecker >())

This feature ensures that.

there exists at least one path from the entry to the exit,
no branch is unresolved.

Default Processor

CFGChecker

◆ CHECKSUM

Identifier<unsigned long > otawa::CHECKSUM("otawa::CHECKSUM", 0)

This property hooked on a CFG provides a checksum build on the instruction of the CFG.

◆ COLLECTED_CFG_FEATURE

p::interfaced_feature<const CFGCollection> otawa::COLLECTED_CFG_FEATURE("otawa::COLLECTED_CFG_FEATURE", new Maker< CFGCollector >())

This feature asserts that all CFG involved in the current computation has been collected and accessible thanks to INVOLVED_CFGS property.

Configuration

Properties

ENTRY_CFG (WorkSpace).
INVOLVED_CFGS (WorkSpace).

Referenced by otawa::DelayedBuilder::cleanup(), otawa::CFGCollection::get(), otawa::cfgio::Input::interfaceFor(), otawa::ai::CFGAnalyzer::process(), otawa::ai::BlockAnalysis< D, S >::processWorkSpace(), and otawa::PSTBuilder::PSTBuilder().

◆ DELAYED_CFG_FEATURE

p::feature otawa::DELAYED_CFG_FEATURE("otawa::DELAYED_CFG_FEATURE", new Maker< DelayedBuilder >())

This feature informs that the current microprocessor supports delayed branches and that the CFG has been changed to reflect effect of delay branches.

Default Processor

otawa::DelayedBuilder

Properties

◆ DELAYED_INST

Identifier<bool> otawa::DELAYED_INST("otawa::DELAYED_INST", false)

This property is set on instruction of a delayed branch.

Features

otawa::DELAYED_CFG_FEATURE

Hooks

otawa::Inst

◆ DELAYED_NOP

Identifier<bool> otawa::DELAYED_NOP("otawa::DELAYED_NOP", false)

This property is true on NOP instructions insserted due to branch delay.

Features

otawa::DELAYED_CFG_FEATURE

Hooks

otawa::Inst

◆ DOMINANCE_FEATURE

p::interfaced_feature<DomInfo> otawa::DOMINANCE_FEATURE("otawa::DOMINANCE_FEATURE", new Maker< Dominance >())

This feature ensures that information about domination between nodes of a CFG is available.

Back edges are marked with BACK_EDGE property while dominance may be tested using an interface of type DomInfo and provided by DOM_INFO property.

OTAWA provides several implementation of domination calculation:

otawa::Dominance

Properties

BACK_EDGE
DOM_INFO

Referenced by otawa::ContextTreeBuilder::ContextTreeBuilder(), otawa::ContextTreeByCFGBuilder::ContextTreeByCFGBuilder(), otawa::EdgeACSBuilder::EdgeACSBuilder(), otawa::EdgeCAT2Builder::EdgeCAT2Builder(), otawa::EdgeCAT2ConstraintBuilder::EdgeCAT2ConstraintBuilder(), otawa::FirstLastBuilder::FirstLastBuilder(), otawa::Dominance::interfaceFor(), otawa::ipet::CachePenaltiesObjectFunctionBuilder::setup(), and otawa::ipet::FlowFactLoader::setup().

◆ ENTRY_CFG

p::id< CFG * > otawa::ENTRY_CFG

This property is used to get the entry CFG of the currently processed task.

@para Hooks

WorkSpace

Referenced by otawa::CFGCollector::cleanup(), otawa::cfgio::Input::cleanup(), otawa::CFGTransformer::commit(), otawa::oslice::Slicer::commit(), otawa::Virtualizer::commit(), otawa::Virtualizer::configure(), otawa::LoopReductor::destroy(), otawa::CFGCollector::destroy(), otawa::CFGTransformer::destroy(), otawa::oslice::Slicer::destroy(), otawa::Virtualizer::destroy(), otawa::ipet::WCETComputation::processWorkSpace(), otawa::display::ILPSystemDisplayer::processWorkSpace(), otawa::ContextTreeBuilder::processWorkSpace(), and otawa::BBRatioDisplayer::setup().

◆ EXIT_LIST

p::id< elm::Vector< Edge * > * > otawa::EXIT_LIST

Defined for any BasicBlock that is a loop header.

Contain a list of the exit edges associated with the loop (more clearly, EXIT_LIST(h) is the list of the edges for which LOOP_EXIT_EDGE(edge) == h)

Hooks

BasicBlock

Referenced by otawa::EXIT_EDGES::begin(), otawa::EXIT_EDGES::end(), otawa::EXIT_EDGES::EXIT_EDGES(), otawa::Loop::exitEdges(), otawa::Loop::exits(), otawa::dfa::hai::HalfAbsInt< otawa::dfa::hai::FirstUnrollingFixPoint >::outputProcessing(), and otawa::ai::FlowAwareRanking::processWorkSpace().

◆ ID

Identifier< const CFGInfo * > & otawa::CFGInfo::ID = CFG_INFO

static

This property allows to get the CFG information from the current CFG is member of.

Hooks

CFG

See also: CFG_INFO

Referenced by otawa::WorkSpace::getCFGInfo().

◆ INLINING_POLICY

Identifier< bool > otawa::INLINING_POLICY

Put on the first instruction of a function to set default inlining behavior during its virtualization.

This overrides VIRTUAL_INLINING default policy of Virtualizer.

FLOW_FACTS_FEATURE
Hooks
Inst

◆ INVOLVED_CFGS

p::id<const CFGCollection *> otawa::INVOLVED_CFGS("otawa::INVOLVED_CFGS", 0)

This property is used to link the current computation involved CFG on the framework.

Hooks

WorkSpace

◆ LOCATION_START

p::id<location_t> otawa::LOCATION_START("otawa::LOCATION_START", location_t(nullptr, nullptr))

Provide the start location of a sub-CFG to extract (inclusive).

Only one start location can be given. If not provided, the start location is assumed to be the first address of the CFG.

Feature

otawa::SPLIT_CFG

Referenced by otawa::SubCFGBuilder::configure().

◆ LOCATION_STOP

p::id<location_t> otawa::LOCATION_STOP("otawa::LOCATION_STOP", location_t(nullptr, nullptr))

Provide the stop location of a sub-CFG to extract (inclusive).

Several stop locations can be given. If not provided, the stop location is assumed to be the last instruction of the blocks preceding the exit of the current CFG.

Feature

otawa::SPLIT_CFG

Referenced by otawa::SubCFGBuilder::configure().

◆ LOOP_ENTRY

p::id<Block*> otawa::LOOP_ENTRY("otawa::LOOP_ENTRY", nullptr)

Is defined for an Edge if this Edge is the entry-edge of any loop.

If this is the case, then, the property contains the header of the loop exited by the edge.

Hooks

Edge

◆ LOOP_EXIT

p::id<Block*> otawa::LOOP_EXIT("otawa::LOOP_EXIT", nullptr)

Is defined for an Edge if this Edge is the exit-edge of any loop.

If this is the case, then, the property contains the header of the loop exited by the edge. If the edge exits more than one loop, the property contains the header of the outer loop.

Hooks

Edge

◆ LOOP_EXIT_EDGE

p::id< Block * > & otawa::LOOP_EXIT_EDGE = LOOP_EXIT

Deprecated:: Use LOOP_EXIT instead.

Referenced by otawa::Loop::isExit(), and otawa::ai::FlowAwareRanking::processWorkSpace().

◆ LOOP_HEADER

Identifier<bool> otawa::LOOP_HEADER("otawa::LOOP_HEADER", false)

Identifier for marking basic blocks that are entries of loops.

Hooks

BasicBlock

Referenced by otawa::ai::PseudoTopoOrder::_topoNodeHelper(), otawa::ipet::EdgeInfoConflict::getLoopHeaderList(), otawa::Loop::isHeader(), otawa::ForwardCFGAdapter::isLoopHeader(), otawa::BackwardCFGAdapter::isLoopHeader(), otawa::Loop::of(), and otawa::dfa::hai::HalfAbsInt< otawa::dfa::hai::FirstUnrollingFixPoint >::outputProcessing().

◆ NO_EXCEPTION

Identifier< bool > otawa::CFGChecker::NO_EXCEPTION

static

In configuration of otawa::CFGChecker .

Inform the CFG checker that it must not issue an exception when an error is found: only a warning.

Referenced by otawa::CFGChecker::configure().

◆ NO_INLINE

Identifier< bool > otawa::NO_INLINE

Put on the first instruction of a function to indicate whether it should be inlined or not during virtualization.

This overrides VIRTUAL_INLINING default policy of Virtualizer and INLINING_POLICY of the caller CFG.

FLOW_FACTS_FEATURE
Hooks
Inst

◆ POSTDOMINANCE_FEATURE

p::interfaced_feature<PostDomInfo> otawa::POSTDOMINANCE_FEATURE("otawa::POSTDOMINANCE_FEATURE", new Maker< PostDominance >())

This feature ensures that information about postdomination between nodes of a CFG is vailable.

Properties

REVERSE_DOM (BasicBlock)

Referenced by otawa::PostDominance::interfaceFor().

◆ SPLIT_CFG

p::feature otawa::SPLIT_CFG

This feature ensure that a part of the current has been extracted as a sub-CFG based on address provided by two properties:

otawa::CFG_START (only one allowed)
otawa::CFG_STOP (several allowed)

This addresses must match instructions of the task entry function and all basic blocks on the paths from start addresses to stop addresses are included in the sub-CFG.

Configuration

Only one otawa::CFG_START or otawa::LOCATION_START can be defined.

Default processor

otawa::SubCFGBuilder

◆ UNROLLED_FROM

Identifier<Block *> otawa::UNROLLED_FROM("otawa::UNROLLED_FROM", 0)

Put on the header ex-header of a loop, this property gives the BB of the unrolled loop.

Hooks

BasicBlock

◆ UNROLLED_LOOPS_FEATURE

p::feature otawa::UNROLLED_LOOPS_FEATURE("otawa::UNROLLED_LOOPS_FEATURE", new Maker< LoopUnroller >())

This feature that the loops have been unrolled at least once.

Configuration

UNROLL_THIS – mark loops to unroll

Properties

UNROLLED_FROM

Classes

Functions

Variables

Detailed Description

Using the CFG

Building the CFGs

Loops in the CFGs

Transforming the CFG

Input / Output in XML

Function Documentation

◆ ADDED_CFG()

◆ ADDED_FUNCTION()

◆ BACK_EDGE()

◆ BB_BOUNDS()

◆ CALLED_BY()

◆ CFG_CHECKSUM_FEATURE()

◆ CFG_INFO()

◆ CFG_INFO_FEATURE()

◆ CFG_START()

◆ CFG_STOP()

◆ CHECKED_CFG_FEATURE()

◆ CHECKSUM()

◆ COLLECTED_CFG_FEATURE()

◆ DELAYED_CFG_FEATURE()

◆ DELAYED_INST()

◆ DELAYED_NOP()

◆ DOMINANCE_FEATURE()

◆ ENTRY_CFG()

◆ EXIT_LIST()

◆ INLINING_POLICY()

◆ INVOLVED_CFGS()

◆ LOCATION_START()

◆ LOCATION_STOP()

◆ LOOP_ENTRY()

◆ LOOP_EXIT()

◆ LOOP_HEADER()

◆ NO_INLINE()

◆ PostDominance()

◆ POSTDOMINANCE_FEATURE()

◆ SPLIT_CFG()

◆ UNROLLED_FROM()

◆ UNROLLED_LOOPS_FEATURE()

Variable Documentation

◆ ADDED_CFG

◆ ADDED_FUNCTION

◆ BACK_EDGE

◆ BB_BOUNDS

◆ CALLED_BY

◆ CFG_CHECKSUM_FEATURE

◆ CFG_INFO

◆ CFG_INFO_FEATURE

◆ CFG_START

◆ CFG_STOP

◆ CHECKED_CFG_FEATURE

◆ CHECKSUM

◆ COLLECTED_CFG_FEATURE

◆ DELAYED_CFG_FEATURE

◆ DELAYED_INST

◆ DELAYED_NOP

◆ DOMINANCE_FEATURE

◆ ENTRY_CFG

◆ EXIT_LIST

◆ ID

◆ INLINING_POLICY

◆ INVOLVED_CFGS

◆ LOCATION_START

◆ LOCATION_STOP

◆ LOOP_ENTRY

◆ LOOP_EXIT

◆ LOOP_EXIT_EDGE

◆ LOOP_HEADER

◆ NO_EXCEPTION

◆ NO_INLINE

◆ POSTDOMINANCE_FEATURE

◆ SPLIT_CFG

◆ UNROLLED_FROM

◆ UNROLLED_LOOPS_FEATURE