Otawa  0.10
Classes | Functions | Variables
branch Plugin

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

Classes

class  otawa::branch::BranchBuilder
 Compute the categories for branch prediction. More...
 
class  otawa::branch::CondNumber
 Associate numbers to each branch relatively to their BHT set. More...
 
class  otawa::branch::OnlyConsBuilder
 This processor add to the current ILP the constraint requires to model the behavior of the BHT. More...
 
class  otawa::branch::ConsBuilder
 This processor add to the current ILP the constraint requires to model the behaviour of the BHT. More...
 

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...
 
Identifier< BasicBlock * > otawa::branch::HEADER ("otawa::branch::HEADER", NULL)
 Loop header of FIRST_UNKNOWN branch prediction category. 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...
 
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...
 
Identifier< int > otawa::branch::COND_NUMBER ("otawa::branch::COND_NUMBER",-1)
 Property giving the number of the control in its BHT set. 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...
 
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 occurences). 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< 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...
 

Variables

Identifier< category_t > otawa::branch::CATEGORY
 Branch prediction category: it is put on the BB containing the branch instruction. More...
 
Identifier< BasicBlock * > otawa::branch::HEADER
 Loop header of FIRST_UNKNOWN branch prediction category. More...
 
p::feature otawa::branch::CATEGORY_FEATURE
 This category assigns to each branch a category according to its branch prediction behavior. More...
 
p::feature otawa::branch::NUMBERED_CONDITIONS_FEATURE
 This feature assign numbers to branch present in a workspace for next processing. More...
 
Identifier< int > otawa::branch::COND_NUMBER
 Property giving the number of the control in its BHT set. 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...
 
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 occurences). 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< 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...
 

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.

This analysis assigns a category to each branch that can be used to evaluate a bound on the number of miss-predictions.

Plugin Information

Function Documentation

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
Hooks
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
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
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
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
Identifier<BasicBlock*> 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
Hooks
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
Hook
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
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 occurences).

Variable Documentation

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
Hooks

Referenced by otawa::branch::OnlyConsBuilder::processBB(), otawa::etime::StandardEventBuilder::processBB(), and otawa::branch::BranchBuilder::processWorkSpace().

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
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

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

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

Referenced by otawa::branch::BranchBuilder::categorize(), otawa::branch::CondNumber::processBB(), otawa::branch::OnlyConsBuilder::processBB(), otawa::branch::ConsBuilder::processBB(), otawa::branch::BranchBuilder::processWorkSpace(), and otawa::BranchProblem::update().

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

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

Identifier<BasicBlock*> 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
Hooks

Referenced by otawa::branch::OnlyConsBuilder::processBB(), otawa::etime::StandardEventBuilder::processBB(), and otawa::branch::BranchBuilder::processWorkSpace().

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
Hook

Referenced by otawa::etime::StandardEventBuilder::handleVariableBranchPred(), otawa::branch::OnlyConsBuilder::processBB(), and otawa::branch::ConsBuilder::processBB().

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
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 occurences).