![]() |
OTAWA
2.0
Framework to perform machine analysis and compute WCET.
|
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... | |
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.
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:
The feature CONSTRAINTS_FEATURE generates ILP constraints to bound the number of mispredictions. Let:
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:
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:
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:
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.
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:
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.
Identifier<int> otawa::branch::COND_NUMBER | ( | "otawa::branch::COND_NUMBER" | , |
- | 1 | ||
) |
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.
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.
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.
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.
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).
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.
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:
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.
Referenced by otawa::branch::BranchBuilder::processWorkSpace(), and otawa::branch::CondNumber::setup().
Identifier<int> otawa::branch::COND_NUMBER("otawa::branch::COND_NUMBER", -1) |
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.
Referenced by otawa::etime::StandardEventBuilder::setup().
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.
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.
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.
Referenced by otawa::branch::CondNumber::setup().
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).