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

Flow-Sensitive Analysis

A flow-sensitive analysis respects the execution order of statements and follows the actual data flow over time. In contrast, a flow-insensitive analysis only considers variable names without their usage order. Flow-insensitive analysis therefore leads to spurious dependencies whenever variables are reassigned for different purposes. Flow-sensitive analysis avoids these false positives by tracing how values are produced and consumed across the program flow.

In the following example, the local variable local1 is reused to store two different intermediate results. A purely name-based (flow-insensitive) analysis would incorrectly consider the output variable out2 dependent on in1 and in2. However, eDA performs a flow-sensitive analysis, which 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

Flow-sensitive analysis is especially important for TargetLink-generated code. TargetLink uses AUX_* variables that are reused for different intermediate results. Without considering the flow, many false dependencies would occur, leading to numerous false positives. In one relevant use case, the number of reported dependencies was reduced by 90% by applying flow-sensitive analysis.

Array-Sensitive Analysis

An array-sensitive analysis distinguishes between different elements of an array whenever they are accessed with constant indices. In contrast, an array-insensitive analysis would treat the whole array as a single variable and report dependencies that are too coarse. By being array-sensitive, eDA can provide more precise results and avoid unnecessary false dependencies.

In the following example, an array A is used to store the input variables in1 and in2. The results show that the array variable A as a whole is dependent on in1 and in2. However, eDA also considers the array elements as separate variables if they are accessed by constant indices. The output variable out1 is therefore only dependent on in1, because it reads from A[0].

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

Array-sensitive analysis is crucial in practice, because many embedded applications rely heavily on arrays for storing intermediate values, lookup tables, or communication buffers. By distinguishing between individual array elements, the number of false positives is reduced significantly, and the resulting dependency information becomes more accurate and actionable.

Field-Sensitive Analysis

Similar to array-sensitive analysis, which distinguishes dependencies between different array elements, a field-sensitive analysis distinguishes dependencies between individual fields of a structured type (e.g. a struct in C). In contrast, a field-insensitive analysis would treat the entire structure as one variable, which may lead to overly conservative results and many false dependencies.

In the following example, a structure S with two fields f1 and f2 is used. The results show that the structure S as a whole depends on both input variables in1 and in2. However, eDA also considers the fields as separate variables, so that out1 is only dependent on in1 via field f1.

Input Code Result 
int in1, in2;
struct {
    int f1;
    int f2;
} S;
int out1;

void func(void) {
    S.f1 = in1;
    S.f2 = in2;

    out1 = S.f1;
}

S: in1 in2
out1: in1

Field-sensitive analysis is particularly important in automotive and embedded applications, where structured data types are frequently used to group related signals (e.g. configuration parameters, sensor clusters, or communication frames). By analyzing fields individually, the precision of the dependency analysis is improved significantly, just as array-sensitive analysis improves the treatment of arrays. This allows engineers to better trace dependencies and reduce false positives in complex software systems.

Call-Sensitive Analysis

A call-sensitive analysis distinguishes between individual function calls and considers the actual arguments used at each call site. In contrast, a call-insensitive analysis would treat all calls to the same function as identical, which can lead to overly coarse dependencies and many false positives. By being call-sensitive, eDA ensures that each invocation of a function is analyzed precisely with respect to its specific inputs and outputs.

In the following example, the helper function add is called three 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 only 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-sensitive analysis is crucial in practice, since functions are often reused with different arguments throughout an application. Without distinguishing between individual calls, dependencies could be over-approximated, reducing the usefulness of the results. By tracking calls separately, the analysis delivers precise and actionable dependency information.

Call by Reference Function Parameters

When functions operate on variables via pointers, the dependency analysis must also follow the indirect modifications caused by these references. Without handling pointer-based updates, only the local assignments inside the function body would be visible, and the true data dependencies would be missed. eDA takes pointer dereferencing into account and correctly tracks how values are changed when passed by reference.

In the following example, the function swap uses pointers to exchange the values of two variables. The function is called twice, but the dependencies remain precise: out1 depends only on in1 and out2 only on in2. No false cross-dependencies are introduced, even though the values are manipulated indirectly through pointers.

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

Handling call by reference is particularly relevant in embedded and automotive applications. APIs such as AUTOSAR often use pointers for efficient data transfer, buffer management, or signal access. By correctly resolving pointer-based updates, the analysis avoids false positives and ensures that the dependencies reflect the actual program behavior.

Pointer Arithmetic

C programs, especially automatically generated code (e.g. by TargetLink), often make use of pointer arithmetic to traverse arrays or tables. In such cases, the dependency analysis must not only follow the pointer itself, but also resolve which data elements are accessed indirectly through arithmetic on the pointer. A naive analysis would treat the pointer as a single variable, leading to overly coarse dependencies. eDA interprets pointer arithmetic and traces how input values influence the traversal and the results.

In the following example, the function index_search increments a pointer through the array table until a condition is no longer satisfied. The index of the last valid element is then returned through the pointer parameter idx. This is a simplified form of code as often generated by TargetLink. The analysis shows that the output variable out1 depends on both the input in1 (the search value) and on the contents of the constant array table.

Input Code Result 
static void index_search(const int *x_table, int x, int *idx) {
    int i = 0;

    while (x >= *(x_table++)) {
        i++;
    }

    *idx = i;
}

const int table[6] = { 1, 2, 3, 5, 7, 11 };
int in1;
int out1;

void func(void) {
    index_search(table, in1, &out1);
}

out1: in1 table

Supporting pointer arithmetic is essential for handling generated code reliably. In practice, this enables precise dependency analysis of table lookups, interpolation routines, and other low-level implementations common in automotive and embedded applications. Without this capability, many unnecessary false dependencies would be introduced, significantly reducing the usefulness of the results.

Note: According to MISRA C guidelines, pointer arithmetic such as x_table++ is prohibited, since it is error-prone and hard to verify. MISRA-compliant code must instead use explicit array indexing (e.g. x_table[i]). Nevertheless, pointer arithmetic still occurs frequently in automatically generated or legacy code, which is why eDA provides full support for it.

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=2836"