Data Structure for Complexity Models
October 20, 2021
Import statement from "ri.newgen"
(Avoids conflicts between number types and types defined by the RI)
The domain Ppolynome is used to represent the complexities of the statement
as function of parameters, variables and indices of loops with lobal coverage. A
Ppolynome is a list of monomials, each monomial being constited of a floating
coefficient and a Pvecteur representing the product of variables with their
Complexity = eval:Ppolynome x varcount x rangecount x ifcount
In the course of the evaluation, a field complexity is associated with each
statement. The sub-domain eval contains a polynome Approching the complexity of
the statement. The sub-domains varcount, rangecount and ifcount give the
information statistics concerning the mnner in which the evaluation of the complexity
took place, therefore also of the complexity itself. They count and in so doing classify
the different types of variables/loops/tests encountered in the course of the
Varcount = symbolic:int x guessed:int x bounded:int x unknown:int
- symbolic = the number of variables which we would like to see appear in
symbolic form in the expression of the complexity (”parameters” Fortran,
loop indices, formal parameters of a subroutine). This gives false resultats
of thois type of variable is modified in the course of execution.
- guessed = the number of variables the values of which which we have
guessed thanks to semantic analysis.
- bounded = the number of variables for whih we have determined a
maximum or minimum thanks to semantic analysis.
- unknown = the number of for which e have found no information, and
which the user has not asked to se displayed in the complexity. These
variables are all replaced by the pseudo-variable UNKNOWN_VARIABLE,
which takes at the end of the evaluation a default value.
Rangecount = profiled:int x guessed:int x bounded:int x unknown:int
- profiled = the number of loops for which the limits have been measured
by means of profiling.
- guessed = the number of loops for which the limits were at worst variable
polynomes of type symbolic or guessed
- bounded = the number of loops for which the min./max limits were
deterlined thanks to semantic analysis.
- unknown = the number of loops for which the number of loops could not
be discovered. In consequence 0 after profiling pass. All these numbers are
replaced by the pseudo-variable: UNKNOWN_RANGE, which will be given
a default value at the end.
Ifcount = profiled:int x computed:int x halfhalf:int
- profiled = the number of tests for which the probability was messured by
mens of profiling .
- computed = the number of tests for which the probability the probability
was calculated. In particular in this case where the boolean expression
depends only on the indices of those loops whose coverage global and whose
ranges are of type guessed.
- halfhalf = the number of tests the probability of which was determined to
be equal to a by defaut.