emmtrix Dependency Analyzer

From emmtrix Wiki
Jump to navigation Jump to search

emmtrix Dependency Analyzer (eDA) analyzes C source code to extract which output signals/variables depend on which input signals/variables.

Dependency Analysis

The core dependency analysis of eDA tool is using the C source code and an entry function (typically a runnable in an automotive application) as input. It calculates which global variables depend on each other when the function is executed. If a variable v1 depends on variable v2, the result of v1 (after function execution) is somehow influenced by the value of v2 (before function execution) when the function is executed.

The dependency analysis is not limited to programs using global variables for transporting information. By applying an automatic preprocessing and postprocessing step, more generic programs can be transformed into programs using global variables. This way we can e.g. detect dependencies between AUTOSAR signals, network communication function, etc.

Simple Case

In the following example, we have the global variables in1, out1, out2 and out3.

  • in1 is assigned to out1, so the value of out1 depend on in1.
  • in1 is not changed in the function, so it is not listed in the results.
  • out2 is assigned a constant value, so it has no dependency on any input value.
  • in1 is added to out3, so the value of out3 depends both on in1 and on out3 itself (i.e. the value prior function execution).
Input Code Result 
int in1;
int out1, out2, out3;

void func(void) {
  out1 = in1;
  out2 = 5;
  out3 += in1;
}

out1: in1
out2: -
out3: out3 in1

Conditional

eDA distinguish between two kinds of dependencies:

  1. Data dependencies are caused by assigning a value to variable.
  2. Control dependencies are caused by the control structure of the program e.g. if a variable changed conditionally. Control dependencies are indicated in the results by the (c) suffix.

eDA restricts that one variable can be either control or data dependent on another variable. The data dependency is considered stronger that the control dependency. If both dependencies appear, only the data dependency will appear in the results.

In this example, the dependency of output variables on input variables is determined based on a conditional if statement. The function checks the value of in1 to decide which values to assign to out1 and out2. The result shows that out1 is control dependent on in1 and data dependent on in2. out2 is both control and data dependent on in1 but only the dominant data dependency is shown.

Input Code Result 
int in1, in2;
int out1, out2;

void func(void) {
    if (in1) {
        out1 = in2;
        out2 = in1;
    } else {
        out1 = 0;
        out2 = 0;
    }
}

out1: in1(c) in2
out2: in1

Delay Elements

In this example, a simple implementation of a delay element is shown. The output variable out1 is assigned the value of in1 from the previous function call. If the function is executed only one time, the output variable is not influenced by any input variable and thus would only have a dependency to the internal variable.

eDA considers this scenario by calculating the dependencies for multiple function calls. If one variable is dependent on a variable from a previous function call, it is considered as a delayed (data or control) dependency. Delayed dependencies are indicated in the results by a suffix of ^-N, where N is the number of function calls the dependency is delayed. Internally non-delayed dependencies are modeled as delayed dependencies with N=0. One variable cannot have multiple delayed or non-delayed dependencies to the same variable. Dependencies with a smaller delay are considered stronger than dependencies with a larger delay.

Input Code Result 
int in1;
int out1;
static int internal1;

void func(void) {
    out1 = internal1;
    
    internal1 = in1;
}

internal1: in1
out1: internal1 in1^-1

Local Variables

In this example, two local variables are used to store intermediate results. eDA considers the local variables and their dependencies to the global variables. The result shows that the output variable out1 is dependent on in1 and in2. The local variables are not listed in the results as their lifetime ends after the function execution.

Input Code Result 
float in1, in2;
float out1;

void func(void) {
    float local1;
    float local2;
    
    local1 = in1 * in1 + in2 * in2;
    local2 = sqrt(local1);
    
    out1 = local2 + 1.0f;
}

out1: in1 in2

Ignoring Name Dependencies

In this example, the local variable local1 is reused to store two different intermediate results. Reusing (global or local) variables is common in C programming and also used by code generators like TargedLink. A name-based dependency analysis would consider the output variable out2 dependent on in1 and in2. However, eDA ignores the name of the variable and considers only the data flow. The result shows that out2 is only dependent on in2.

Input Code Result 
float in1, in2;
float out1, out2;

void func(void) {
    float local1;

    local1 = in1 * in1;
    out1 = local1;
    
    local1 = sqrt(in2);
    out2 = local1;
}

out1: in1
out2: in2

Ignoring name dependencies is especially important for TargetLink-generated code. TargetLink uses `AUX_*` variables that are reused for different intermediate results. Name dependencies would lead to many false dependencies and thus to many false positives. In one relevant use case, the number of dependencies was reduced by 90% by ignoring name dependencies.

Arrays

In this example, an array A is used to store the input variables in1 and in2. The results show that the array variable A is dependent on in1 and in2. However, eDA considers the array elements as separate variables if they are accessed by constant indices. The output variable out1 is only dependent on in1.

Input Code Result 
int in1, in2;
int A[10];
int out1;

void func(void) {
    A[0] = in1;
    A[1] = in2;
    
    out1 = A[0];
}

A: in1 in2
out1: in1

Function Calls

In this example, the function add is used to calculate the sum of two input variables. The function is called 3 times with different arguments. eDA not only considers the data dependencies between the parameters and the return value but also calculates the dependencies for each call separately. The result shows that out1 is dependent on in1 and in2, out2 is dependent on in1 and out3 is independent of any input variable.

Input Code Result 
int in1, in2;
int out1, out2, out3;

int add(int a, int b) {
	return a + b;
}

void func(void) {
	out1 = add(in1, in2);
	out2 = add(in1, 1);
    out3 = add(5, 6);
}

out1: in1 in2
out2: in1
out3: -

Call by Reference Function Parameters

In this example, the function swap uses pointers to swap the values of two input variables. ...

Input Code Result 
int in1, in2;
int out1, out2;

void swap(int* a, int* b) {
    int c = *a;
    *a = *b;
    *b = c;
}

void func(void) {
    out1 = in1;
    out2 = in2;

    swap(&out1, &out2);
    swap(&out1, &out2);
}

out1: in1
out2: in2

Parametrized Dependency Analysis

In automotive applications, it is common to use the same software across multiple car models with different configurations. eDA supports a parametrized dependency analysis where one or more input variables are considered as constant parameters. Code parts that are deactivated by the constant parameters are not considered during dependency analysis. This is useful to calculate the dependencies only for one active configuration and to reduce the number of dependencies.

eDA follows a two step approach for the parametrized dependency analysis. In the first step, the constant parameters are propagated through the code and inactive code parts are removed. In the second step, the dependency analysis is performed on the transformed code. Even the transformed code is available as intermediate code for transparency reasons. This is useful to understand the results and to verify the correctness of the transformation.

The following example is identical to the conditional example. Only the input variable in1 is considered as a constant parameter (indicated by the static const in the input code). The result shows the intermediate code after the transformation. The if statement is removed and the output variables are assigned the values of the else branch. In contrast to the conditional example, the output variables are not dependent on the input variable in1.

Input Code Intermediate Code Result 
static const int in1 = 0;
int in2;
int out1, out2;

void func(void) {
    if (in1) {
        out1 = in2;
        out2 = in1;
    } else {
        out1 = 0;
        out2 = 0;
    }
}

int in2;
int out1, out2;

void func(void) {
    out1 = 0;
    out2 = 0;
}

out1: -
out2: -

AUTOSAR Integration

In AUTOSAR, ports are accessed using IRead/IWrite function. By providing dummy implementations of these functions that simple read or write a dummy global variable, the AUTOSAR program is transformed into a program with global variables. This is used as input for the dependency analysis.

Output Format Example

A small source code example is shown in the next figure. The code uses three global variables g1. g2 and g3 as well as two output variables out1 and out2. The dependency analysis extracts how the output depend on the input variables.

emmtrix Dependency Analyzer -Input

The results are shown in the XML file in the next figure. Variable out1 depends on g3 and g2 whereas the dependency to g3 is a control dependency and to g2 a data dependency. Variable out2 only depends on g1.

emmtrix Depenendy Analyzer xml results.png


More information can be seen as comments inside of the C code. The next figure shows all use (read) and def (write) accesses to all variables in the program. Control dependencies are marked with (c), delayed dependencies that depend on values from a previous iteration by ^-1. Phi statements are virtual instructions that are placed when the value of a variable depends on a condition. This kind of representation is useful to see the dependencies directly where they come from in the source code.

An extract from the full dependency graph can be seen in the next figure. It shows statements from the source code and how they depend on each other:

  • SSA: there exists a use/def dependency where one signal writes a value  and another one reads it
  • Control: a control dependency caused by a condition (branch) instruction exists
  • CallArg:  the statement depends on an argument of the function
  • Expr:  the statement is part of the previous expression.

This kind of visualization can help pinpoint the root of a specific dependency.

Undescribed Features

  • Function calls to known functions
  • Function calls to unknown functions
  • Loops
  • Switch case
  • Output
    • C debug output
    • XML output
    • Reachability output
    • Dependency path output
  • Propagation of tags (e.g. OBD, ASIL-D)
  • AUTOSAR integration
  • Bitblast Transformation

See Also

Interested?

Interested in applying this coverage workflow to your own projects?

→ Contact us at emmtrix.com/company/contact.

Retrieved from "https://www.emmtrix.com/w139/index.php?title=emmtrix_Dependency_Analyzer&oldid=2816"