This plugins implements the analysis for branch predictor proposed in paper below: More...

Classes
class	otawa::branch::BranchBuilder

class	otawa::branch::CondNumber

class	otawa::branch::ConsBuilder

class	otawa::branch::OnlyConsBuilder

Functions
Identifier< category_t >	otawa::branch::CATEGORY ("otawa::branch::CATEGORY", branch::NOT_CLASSIFIED)
	Branch prediction category: it is put on the BB containing the branch instruction. More...

p::feature	otawa::branch::CATEGORY_FEATURE ("otawa::branch::CATEGORY_FEATURE", new Maker< BranchBuilder >())
	This category assigns to each branch a category according to its branch prediction behavior. More...

Identifier< int * >	otawa::branch::COND_MAX ("otawa::branch::COND_MAX", NULL)
	This features returns an array integer giving, for each BHT set, the maximum number of branches in the workspace. More...

Identifier< int >	otawa::branch::COND_NUMBER ("otawa::branch::COND_NUMBER", -1)
	Property giving the number of the control in its BHT set. More...

p::feature	otawa::branch::CONSTRAINTS_FEATURE ("otawa::branch::CONSTRAINTS_FEATURE", new Maker< OnlyConsBuilder >)
	This feature adds to the ILP system the constraints modelling the number of misspredictions and a variable representing this number. More...

Identifier< Block * >	otawa::branch::HEADER ("otawa::branch::HEADER", NULL)
	Loop header of FIRST_UNKNOWN branch prediction category. More...

Identifier< ilp::Var * >	otawa::branch::MISSPRED_VAR ("otawa::branch::MISSPRED_VAR", NULL)
	This properties gives the variables counting the number of miss-prediction for a basic block ending with a control instruction. More...

p::feature	otawa::branch::NUMBERED_CONDITIONS_FEATURE ("otawa::branch::NUMBERED_CONDITIONS_FEATURE", new Maker< CondNumber >())
	This feature assign numbers to branch present in a workspace for next processing. More...

p::feature	otawa::branch::SUPPORT_FEATURE ("otawa::branch::SUPPORT_FEATURE", new Maker< ConsBuilder >())
	This feature adds to the objective function of the ILP system the raw cost of the BHT behaviour (that is the branch misprediction penalties multiplied by the number of occurrences). More...

Variables
Identifier< category_t >	otawa::branch::CATEGORY
	Branch prediction category: it is put on the BB containing the branch instruction. More...

p::feature	otawa::branch::CATEGORY_FEATURE
	This category assigns to each branch a category according to its branch prediction behavior. More...

Identifier< int * >	otawa::branch::COND_MAX
	This features returns an array integer giving, for each BHT set, the maximum number of branches in the workspace. More...

Identifier< int >	otawa::branch::COND_NUMBER
	Property giving the number of the control in its BHT set. More...

p::feature	otawa::branch::CONSTRAINTS_FEATURE
	This feature adds to the ILP system the constraints modelling the number of misspredictions and a variable representing this number. More...

Identifier< Block * >	otawa::branch::HEADER
	Loop header of FIRST_UNKNOWN branch prediction category. More...

Identifier< ilp::Var * >	otawa::branch::MISSPRED_VAR
	This properties gives the variables counting the number of miss-prediction for a basic block ending with a control instruction. More...

p::feature	otawa::branch::NUMBERED_CONDITIONS_FEATURE
	This feature assign numbers to branch present in a workspace for next processing. More...

p::feature	otawa::branch::SUPPORT_FEATURE
	This feature adds to the objective function of the ILP system the raw cost of the BHT behaviour (that is the branch misprediction penalties multiplied by the number of occurrences). More...

Detailed Description

This plugins implements the analysis for branch predictor proposed in paper below:

A. Colin, I. Puaut. Worst case execution time analysis for a processor with branch prediction (BTB with 2-bit counter and saturation). Real-Time Systems, Special issue on worst-case execution time analysis, 2000.

Category Building

The feature CATEGORY_FEATURE assigns a category to each branch that can be used to evaluate a bound on the number of miss-predictions. The supported categories are:

ALWAYS_D – never present in the BTB and default policy applies (taken),
ALWAYS_H – always present in the BTB,
FIRST_UNKNOW – always present in the BTB except for the first iteration,
NOT_CLASSIFIED – none of the previous categories applies.

Constraint Building

The feature CONSTRAINTS_FEATURE generates ILP constraints to bound the number of mispredictions. Let:

x_i – the number of execution of basic block i on WCET path,
x^mp_i – the number of misprediction for basic block i,
e^nt_i – number of execution of not-taken edge from i,
e^t_i – number of execution of taken edge from i,
x_h – number of execution of header associated with FIRST_UNKNOWN. The following constraints are generated:
0 <= x^mp_i <= x_i
x^mp_i = x^nt_i if category is ALWAYS_D
x^mp_i <= 2 e^t_i + 2 if category is ALWAYS_H
x^mp_i <= 2 e^nt_i + 2 if category is ALWAYS_H
x^mp_i <= 2 e^t_i + 2 x_h if category is FIRST_UNKOWN
x^mp_i <= 2 e^nt_i + 2 x_h if category is FIRST_UNKOWN

WCET Contribution

The feature SUPPORT_FEATURE increase the WCET objective function with the rough evaluation of misprediction cost in cycles dependeing on the branch type: direct conditional, indirect inconditional and conditional. The term below is added to the objective function:

x^mp_i * t_mp with t_mp the cost of misprediction (from BHT configuration).

Events

Finally, EVENT_FEATURE ensures that the misprediction has been translated as event object as used by the Event Time Module plugin and stored on basic block to be used for event-based WCET computation.

Several events are created and put on the edges according two policies, taken (T) and not-taken(T).

In the simpler case, ALWAYS_D, the occurrence is:

NEVER on the default prediction direction,
ALWAYS in the reverse case (bounded the edge occurrences).

For others categories, one variable for each edge needs to be created that will be abstracted by x_T (taken) and x_NT (not-taken) and, respectively, x^mp_T and x^mp_NT for misprediction number. The following constraints are added:

x^mp_T + x^mp_NT = x^mp_i
x^mp_T <= x_T (no more mispredictions than edge taken),
x^mp_NT <= x_NT

Hardware Domain: It applies only on branch predictors made of a BTB with a 2-bit counter with saturation.

Configuration: Misprediction costs are taken from otawa::hard::BHT.

Plugin Information

name: otawa/branch
header: <otawa/branch/features.h>

Function Documentation

◆ CATEGORY()

Identifier<category_t> otawa::branch::CATEGORY	(	"otawa::branch::CATEGORY"	,
		branch::NOT_CLASSIFIED
	)

Branch prediction category: it is put on the BB containing the branch instruction.

Feature

CATEGORY_FEATURE

Hooks

BasicBlock

◆ CATEGORY_FEATURE()

p::feature otawa::branch::CATEGORY_FEATURE	(	"otawa::branch::CATEGORY_FEATURE"	,
		new Maker< BranchBuilder >	()
	)

This category assigns to each branch a category according to its branch prediction behavior.

The following branch prediction categories are supported:

ALWAYS_D – always predicted with default branch prediction
ALWAYS_H – always prediction is in the BHT
FIRST_UNKNOWN – first prediction unknown, other prediction in the BHT.
NOT_CLASSIFIED – the behavior cannot precisely be analyzed.

Properties

◆ COND_MAX()

Identifier<int *> otawa::branch::COND_MAX	(	"otawa::branch::COND_MAX"	,
		NULL
	)

This features returns an array integer giving, for each BHT set, the maximum number of branches in the workspace.

Feature

NUMBERED_CONDITIONS_MAKER

Hook

WorkSpace

◆ COND_NUMBER()

Identifier<int> otawa::branch::COND_NUMBER	(	"otawa::branch::COND_NUMBER"	,
		-	1
	)

Property giving the number of the control in its BHT set.

Feature

NUMBERED_CONDITIONS_MAKER

Hook

BasicBlock

◆ CONSTRAINTS_FEATURE()

p::feature otawa::branch::CONSTRAINTS_FEATURE	(	"otawa::branch::CONSTRAINTS_FEATURE"	,
		new Maker< OnlyConsBuilder >
	)

This feature adds to the ILP system the constraints modelling the number of misspredictions and a variable representing this number.

Properties

MISSPRED_VAR

◆ HEADER()

Identifier<Block*> otawa::branch::HEADER	(	"otawa::branch::HEADER"	,
		NULL
	)

Loop header of FIRST_UNKNOWN branch prediction category.

If the loop iterates at most N times, the first time has an unknown behaviour and, in the N-1 next iterations, the predicted target is in the BHT.

Feature

CATEGORY_FEATURE

Hooks

BasicBlock

◆ MISSPRED_VAR()

Identifier<ilp::Var*> otawa::branch::MISSPRED_VAR	(	"otawa::branch::MISSPRED_VAR"	,
		NULL
	)

This properties gives the variables counting the number of miss-prediction for a basic block ending with a control instruction.

Feature

SUPPORT_FEATURE

Hook

BasicBlock

◆ NUMBERED_CONDITIONS_FEATURE()

p::feature otawa::branch::NUMBERED_CONDITIONS_FEATURE	(	"otawa::branch::NUMBERED_CONDITIONS_FEATURE"	,
		new Maker< CondNumber >	()
	)

This feature assign numbers to branch present in a workspace for next processing.

Properties

◆ SUPPORT_FEATURE()

p::feature otawa::branch::SUPPORT_FEATURE	(	"otawa::branch::SUPPORT_FEATURE"	,
		new Maker< ConsBuilder >	()
	)

This feature adds to the objective function of the ILP system the raw cost of the BHT behaviour (that is the branch misprediction penalties multiplied by the number of occurrences).

Variable Documentation

◆ CATEGORY

Identifier<category_t> otawa::branch::CATEGORY("otawa::branch::CATEGORY", branch::NOT_CLASSIFIED)

Branch prediction category: it is put on the BB containing the branch instruction.

Feature

CATEGORY_FEATURE

Hooks

BasicBlock

◆ CATEGORY_FEATURE

p::feature otawa::branch::CATEGORY_FEATURE("otawa::branch::CATEGORY_FEATURE", new Maker< BranchBuilder >())

This category assigns to each branch a category according to its branch prediction behavior.

The following branch prediction categories are supported:

ALWAYS_D – always predicted with default branch prediction
ALWAYS_H – always prediction is in the BHT
FIRST_UNKNOWN – first prediction unknown, other prediction in the BHT.
NOT_CLASSIFIED – the behavior cannot precisely be analyzed.

Properties

◆ COND_MAX

Identifier<int *> otawa::branch::COND_MAX("otawa::branch::COND_MAX", NULL)

This features returns an array integer giving, for each BHT set, the maximum number of branches in the workspace.

Feature

NUMBERED_CONDITIONS_MAKER

Hook

WorkSpace

Referenced by otawa::branch::BranchBuilder::processWorkSpace(), and otawa::branch::CondNumber::setup().

◆ COND_NUMBER

Identifier<int> otawa::branch::COND_NUMBER("otawa::branch::COND_NUMBER", -1)

Property giving the number of the control in its BHT set.

Feature

NUMBERED_CONDITIONS_MAKER

Hook

BasicBlock

◆ CONSTRAINTS_FEATURE

p::feature otawa::branch::CONSTRAINTS_FEATURE("otawa::branch::CONSTRAINTS_FEATURE", new Maker< OnlyConsBuilder >)

This feature adds to the ILP system the constraints modelling the number of misspredictions and a variable representing this number.

Properties

MISSPRED_VAR

Referenced by otawa::etime::StandardEventBuilder::setup().

◆ HEADER

Identifier<Block*> otawa::branch::HEADER("otawa::branch::HEADER", NULL)

Loop header of FIRST_UNKNOWN branch prediction category.

If the loop iterates at most N times, the first time has an unknown behaviour and, in the N-1 next iterations, the predicted target is in the BHT.

Feature

CATEGORY_FEATURE

Hooks

BasicBlock

◆ MISSPRED_VAR

Identifier<ilp::Var*> otawa::branch::MISSPRED_VAR("otawa::branch::MISSPRED_VAR", NULL)

This properties gives the variables counting the number of miss-prediction for a basic block ending with a control instruction.

Feature

SUPPORT_FEATURE

Hook

BasicBlock

◆ NUMBERED_CONDITIONS_FEATURE

p::feature otawa::branch::NUMBERED_CONDITIONS_FEATURE("otawa::branch::NUMBERED_CONDITIONS_FEATURE", new Maker< CondNumber >())

This feature assign numbers to branch present in a workspace for next processing.

Properties

Referenced by otawa::branch::CondNumber::setup().

◆ SUPPORT_FEATURE

p::feature otawa::branch::SUPPORT_FEATURE("otawa::branch::SUPPORT_FEATURE", new Maker< ConsBuilder >())

This feature adds to the objective function of the ILP system the raw cost of the BHT behaviour (that is the branch misprediction penalties multiplied by the number of occurrences).

Classes

Functions

Variables

Detailed Description

Function Documentation

◆ CATEGORY()

◆ CATEGORY_FEATURE()

◆ COND_MAX()

◆ COND_NUMBER()

◆ CONSTRAINTS_FEATURE()

◆ HEADER()

◆ MISSPRED_VAR()

◆ NUMBERED_CONDITIONS_FEATURE()

◆ SUPPORT_FEATURE()

Variable Documentation

◆ CATEGORY

◆ CATEGORY_FEATURE

◆ COND_MAX

◆ COND_NUMBER

◆ CONSTRAINTS_FEATURE

◆ HEADER

◆ MISSPRED_VAR

◆ NUMBERED_CONDITIONS_FEATURE

◆ SUPPORT_FEATURE