Zhenyu Bai

Hugues Cassé

Thomas Carle

Christine Rochange

Computing Execution Times with eXecution Decision Diagrams in the Presence of Out-Of-Order Resources

Keywords: real-time, WCET, static analysis, pipeline

. To remain sound, the timing analysis must either rely on huge timing over-estimations or consider all possible pipeline states which usually leads to a combinatorial blowup. To cope with this situation, we build an efficient computational model by leveraging the algebraic properties of the eXecution Decision Diagram [2] which is able to track precisely all pipeline states all along the execution paths of the analysed program while keeping the analysis time within acceptable range. We show how to apply this analysis at the Control Flow Graph (CFG) level, and how to account for a typical out-of-order resource: the shared memory bus between the instruction and data caches. We observe a gain in precision of the WCET ranging from 20% to 80% compared to the state-of-the-art pipeline analysis of the OTAWA WCET toolset. The analysis time shows that our approach scales to realistic benchmarks, making it appropriate for industrial applications.

I. INTRODUCTION

The correctness of hard real-time systems depends not only on their functional behavior but also on their temporal behavior. The latter is guaranteed by the scheduling analysis of the tasks composing the system, which relies on the estimation of their Worst-Case Execution Time (WCET).

With modern processors, the execution time of a code snippet is difficult to determine. For instance, on a processor equipped with cache memories, the latency of memory accesses is variable: it depends on whether the access results in a Cache Miss or a Cache Hit. The presence, in modern micro-architectures, of pipelined and superscalar execution and other mechanisms to favor instruction-level parallelism and achieve high performance generates a large variability of execution times and makes the WCET analysis suffer from timing anomalies [START_REF] Lundqvist | Timing anomalies in dynamically scheduled microprocessors[END_REF]- [START_REF] Cassez | What is a timing anomaly?[END_REF]. Briefly, timing anomalies imply that the WCET analysis cannot assume that a local worst case will lead to the global worst case. Illustrated on the case of cache accesses, this means that a cache miss (longer access) cannot be assumed to lead to the global worst case, and whether or not it contributes to the global WCET is not determined [START_REF] Reineke | A Definition and Classification of Timing Anomalies[END_REF], [START_REF] Wenzel | Principles of timing anomalies in superscalar processors[END_REF]. Unless the target processor is proven to be free of timing anomalies, a safe and precise WCET analysis has to capture them by precisely tracking the execution states of the microarchitecture.

The WCET computation is generally broken down into three parts [START_REF] Wilhelm | Static Timing Analysis for Hard Real-Time Systems[END_REF]. First, global analyses, independent of the pipeline's structure, are performed: they typically encompass cache and branch-prediction analyses, which determine the behavior of these mechanisms at instruction level. Second, the pipeline analysis uses the information provided by global analyses to determine how instructions are executed through the pipeline, and to compute the (worst-case) execution times of basic blocks (BB). Finally, an ILP system is built to maximize the execution time considering the individual WCETs of basic blocks computed in the previous step, with constraints expressing the structure of the CFG and flow facts, such as loop bounds. The solution of the ILP system is the WCET of the whole program. This method is called Implicit Path Enumeration Technique (IPET) [START_REF] Li | Performance analysis of embedded software using implicit path enumeration[END_REF].

The most important bottleneck in the classical structure of WCET analysis is the lack of efficient abstraction of pipeline. Existing approaches either tend to be not scalable or imprecise. However, our previous approach [START_REF] Bai | Improving the Performance of WCET Analysis in the Presence of Variable Latencies[END_REF] shows that the eXecution Decision Diagram (XDD) is a good data structure to record times within the pipeline analysis that improves its performance. An XDD can be deemed as a lossless compression of the relationship between the execution time and the combination of timing variations. By implanting XDD into the Execution Graph (XG) pipeline model, we achieved exact and efficient pipeline analysis on basic blocks through in-order pipelines. In [START_REF] Bai | Improving the Performance of WCET Analysis in the Presence of Variable Latencies[END_REF], the pipeline analysis is designed to consider BBs of a program independently by calculating their worstcase execution context. However, with out-of-order accesses to resources such as shared buses, the conservative use of a worstcase context does not hold anymore. We need to precisely track the possible execution contexts in order to evaluate how the concurrent accesses to the bus are interleaved. The pipeline analysis has to analyze the micro-architecture states on the whole program, that is, at Control-Flow Graph (CFG) level.

a) Contributions: This paper presents (a) how we adapt the original graph based pipeline model proposed in [START_REF] Bai | Improving the Performance of WCET Analysis in the Presence of Variable Latencies[END_REF] into a data-flow analysis applied at CFG level that computes exactly all the possible temporal pipeline states; (b) how we construct an efficient computational model of our analysis by leveraging the algebraic properties of XDD, which turns the state transition into matrix multiplication on a semi-ring; (c) how we exploit the precise pipeline states produced by this computational model to support a typical out-of-order resource: the memory bus that is shared by the instruction and data caches to access the main memory; and (d) the evaluation of our model on realistic applications (TACLe's benchmarks [START_REF] Falk | Taclebench: A benchmark collection to support worst-case execution time research[END_REF]) that shows its scalability. Several parameters are measured during the experiment to give some explanation of its good performance. The precision gain of our approach is compared with the state-of-the-art pipeline analysis of OTAWA [START_REF] Ballabriga | Otawa: An open toolbox for adaptive wcet analysis[END_REF] and shows improvement of the final WCET ranging from 20% to 80%.

b) Outline: First, the related works are discussed in Section II. Section III provides background information on the XG model and the XDD structure. In Section IV, we extend the original model of XG with XDD to a resourcebased model which is able to express the state of the pipeline with a vector. Later in this section, we show how to leverage the algebraic properties of XDD in order to improve the performance of the analysis by pre-computing the calculus as matrices. In Section V, we show how to build the complete analysis at CFG level. Section VI extends our model to support the shared memory bus. Experiments reported in Section VII demonstrate the efficiency and the precision of our analysis on realistic benchmarks. Several metrics are considered and discussed, and we conclude in Section VIII.

II. RELATED WORK

The most complex part of the classical structure of WCET analysis (global analyses + pipeline analysis + IPET) is the pipeline analysis because of the presence of timing anomalies and the complexity of modern micro-architectures. We may classify the state-of-the-art pipeline analyses into two classes: those at CFG level and those at BB level.

The aiT analyzer is one of the most successful WCET analysis tools and it performs pipeline analysis at CFG level [START_REF] Schneider | Pipeline behavior prediction for superscalar processors by abstract interpretation[END_REF], [START_REF] Thesing | Safe and precise wcet determination by abstract interpretation of pipeline models[END_REF]. Concretely, it builds an abstract model of the pipeline: this model describes the transition of pipeline states at the granularity of processor cycles. Its pipeline analysis, based on the abstract interpretation framework [START_REF] Cousot | Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF], computes an overset of the possible pipeline states over the CFG of the program. To the best of our knowledge, it uses power set domain to keep the set of possible pipeline states. Therefore, this model suffers from combinatorial complexity caused by the presence of timing anomalies as it has to keep all possible states. Several approaches were proposed to reduce the complexity: (a) although the literature provides very few details about that, close states seem to be joined to form abstract states at the cost of a loss of precision, (b) in [START_REF] Wilhelm | Symbolic representations in WCET analysis[END_REF], the authors show how to use a Binary Decision Diagram to compress the state machine representation of their analysis system, and (c) in [START_REF] Reineke | Sound and Efficient WCET Analysis in the Presence of Timing Anomalies[END_REF] Reineke et al. define a sufficient condition to drop not-worst cases in order to reduce the number of states. This work has been extended later in [START_REF] Hahn | Toward Compact Abstractions for Processor Pipelines[END_REF], [START_REF] Hahn | Design and analysis of SIC: a provably timingpredictable pipelined processor core[END_REF], providing a theoretical basis to design strictly-in-order pipeline where timing anomalies are proven to not occur [START_REF] Wenzel | Principles of timing anomalies in superscalar processors[END_REF], [START_REF] Engblom | Processor pipelines and their properties for static WCET analysis[END_REF], thus allowing to more easily drop non-worst case states.

Another approach to pipeline analysis is to compute locally the WCET per BB. The Execution Graph proposed by Li et al. [START_REF] Li | Modeling out-of-order processors for software timing analysis[END_REF] (chronos analyzer) is a very representative example. Instead of computing the pipeline state over the CFG, they make assumptions about the worst execution context of each BB. To avoid using powerset domain to keep the pipeline states, they use interval domain to keep the minimal and maximal execution times of instructions. The contention between instructions is considered by checking the intersection of time intervals. If a contention occurs, the interval is extended accordingly. The XG solving algorithm repeats the computation until a fix point is reached. However, in the presence of lots of events, the interval representation tends to trigger a chain reaction: the imprecision due to the interval representation creates contentions that are actually impossible, which extends the interval and involves more impossible contentions -hence introducing considerable overestimation. Moreover, with respect to the micro-architecture, making precise assumptions on the worst execution context is not always simple. Another XG-based approach is proposed by Rochange et al. in [START_REF] Rochange | A Context-Parameterized Model for Static Analysis of Execution Times[END_REF] that computes the execution time of BBs for each combination of events, which makes the algorithm tending towards combinatorial complexity. In addition, the contention analysis requires examining all cases, leading to an exponential complexity.

Another different direction of static WCET analysis uses model checking approaches. The principle of these approaches is to express the analyzed program and the complete microarchitecture (including cache, pipeline and all timing related components) by a timed automaton without abstraction. The WCET is computed by exploring all possible states of the automaton. Since all states are reached, it is compatible with timing anomalies by nature. These approaches usually provide exact WCETs and are able to give the longest path, which may help the developers to further optimize the WCET. On the other hand, they generally have scalability issues when the micro-architecture becomes complex (this results in a larger pipeline state domain) or when the program under analysis becomes complex (this results in an intractable amount of execution traces to explore). One of the most well known tools in this category is UPPAAL [START_REF] Behrmann | [END_REF]. To the best of our knowledge, the best experiment using UPPAAL, reported in [START_REF] Cassez | Timed games for computing wcet for pipelined processors with caches[END_REF], is not able to analyze all the benchmarks of the Mälardalen suite, but only the simplest ones. Some hypotheses are also made to turn some programs into single-path programs, which greatly reduces the complexity of the problem.

In [START_REF] Lim | An accurate worst case timing analysis for risc processors[END_REF], the authors compute the WCET of BBs with reservation tables that simulate the reservation of resources in the pipeline at each cycle. The worst reservation hence gives the worst execution time. In [START_REF] Colin | A modular and retargetable framework for treebased wcet analysis[END_REF], the worst behavior of the pipeline, caches and branch predictors are obtained by simulations at BB-level. In [START_REF] Kirner | Precise worst-case execution time analysis for processors with timing anomalies[END_REF], the worst timing contributions of different components (cache, pipeline and others) are computed separately and then safely composed using rules defined in the paper. In [START_REF] Engblom | Processor pipelines and their properties for static wcet analysis[END_REF], the authors bound the distance of temporal effects between instructions, so as to compute the WCET per instruction with a safe over-estimation.

Our analysis: The pipeline model proposed in this paper is inspired from a key idea of the XG approach: it uses dependencies to describe the temporal behavior of the pipeline, which allows the analysis to work at pipeline stage level (unlike aiT that works at the granularity of processor cycles). Our strategy improves the efficiency of the analysis because one dependency often spans over several processor cycles, which leads to a reduced number of applied transitions and a more compact dependency representation.

Compared to the original XG approach, this new model considers the effect of instructions of other BBs on the timing of the analyzed BB (instead of considering each BB in isolation), and it uses XDDs (instead of the interval domain in the original XG, or the powerset domain in the case of aiT) to efficiently represent all possible pipeline states without loss of precision. Theoretically, this approach is thus more precise than the original XG approach, and more efficient than the approach used by aiT when tracking explicitly all possible pipeline states.

III. BACKGROUND

As a program under analysis usually has several execution paths and possibly loops, it is impossible to track all the possible execution traces. The static WCET analysis approach we use in this paper models the whole program as a CFG, then computes the WCET of each BB and determines the WCET using the IPET method. Thus, the pipeline analysis aims at determining the execution time of each BB, for example, using Execution Graphs.

A. Execution Graphs

An eXecution Graph (XG) [START_REF] Li | Modeling out-of-order processors for software timing analysis[END_REF], [START_REF] Rochange | A Context-Parameterized Model for Static Analysis of Execution Times[END_REF] models the temporal behavior of an instruction sequence (such as a BB) executed in the pipeline. The key idea of the XG is to model the temporal behavior by considering the dependencies arising between instructions during their execution in the pipeline stages. For example, an instruction has to leave a pipeline stage before starting its execution in the next stage, an instruction has to read a register after a prior instruction has written this register, etc. This results in a dependency graph: a vertex represents the progress of an instruction in a pipeline stage; the edges represent the precedence relationships between these vertices. Formally, let I be the set of machine instructions, and let G XG be a Directed Acyclic Graph (DAG) G XG = ⟨V XG , E XG ⟩ built for an instruction sequence I * such that

• V XG is the set of vertices defined by V XG = {[I i /s] | I i ∈ I * ∧ s ∈ P}, with P the set of pipeline stages. • E XG ⊂ V XG × V XG ,
the set of edges, is built according to the dependencies in the considered pipeline. In addition, an XG is decorated with temporal information:

• λ v ∈ N is the latency of vertex v,
IC 0 IC 0 IC 0 IC 1 IC 1 IC 1 DC 2 DC 2 DC 2
Fig. 1: XG model of an instruction sequence.

Examples in this paper consider a 5-stage (FE -fetch, DE -decode, EX -execute, ME -memory, WB -write-back) inorder 2-way superscalar pipeline but the presented algorithms are not limited to this configuration. Figure 1 shows the XG for this pipeline and for the sequence of instructions listed on the left. The vertices correspond to the use of a pipeline stage (column headers) by an instruction (row headers). The edges reflect the following dependencies:

• The horizontal solid edges model the Pipeline Order: an instruction goes through pipeline stages in a given order. between instructions, when an instruction reads a register written by a prior instruction. The set of dependency edges shown above is typical for inorder pipelines. Depending on a particular pipeline design, rules to build the edges may be added or removed to account for specific features.

Using an XG, the start time of an instruction in a stage ρ w is computed as the earliest time at which all incoming dependencies are satisfied and the end time ρ * w as ρ w increased by the time passed by the instruction in the stage:

ρ w = max v→w∈EXG ρ v + δ v→w × λ v ρ * w = ρ w + λ w (1)
The execution time of the instruction sequence is obtained by calculating the start time of each vertex following a topological order in the XG. Since the pipeline is in-order (all resources are allocated in the program order), the timing of an instruction only depends on prior instructions, meaning that, at least, one topological order exists. For in-order processors, this order is implied by the combination of the Pipeline Order (horizontal edges) and of the Capacity Order (vertical edges). It is highlighted in the example XG of Figure 1 by the light gray arrow in the background.

The computation of an XG is fast and efficient. However, as soon as the pipeline produces variable latencies (e.g. to reflect a possible cache hit or miss), precision is achieved at the cost of computing the XG for each combination of these latencies. This may engender a computation complexity explosion. The data structure presented in the next section alleviates this issue.

B. Execution Decision Diagrams

The eXecution Decision Diagram (XDD) is inspired from the Binary Decision Diagram (BDD) [START_REF] Akers | Binary decision diagrams[END_REF], [START_REF] Bryant | Symbolic boolean manipulation with ordered binarydecision diagrams[END_REF] and its Multi-Terminal BDD (MTBDD) variant [START_REF] Fujita | Multi-terminal binary decision diagrams: An efficient data structure for matrix representation[END_REF]. An XDD is a DAG that is recursively defined as:

Definition III.1. XDD = LEAF(k) | NODE(e, f , f ) (2)
The Boolean variables e ∈ E in nodes are called events: they model the uncertainty in the analysis regarding the microarchitecture state and its impact on the time, e.g. whether a particular cache access results in a hit or in a miss. The subtrees f, f ∈ XDD represent, respectively, the situations where the event e happens or not. The leaves of an XDD store the execution times k ∈ Z # = Z ∪ {+∞, -∞}.

As in ordered BDDs [START_REF] Bryant | Symbolic boolean manipulation with ordered binarydecision diagrams[END_REF], XDDs deploy hash consing techniques to guarantee the unicity of the sub-tree instances and speed up the calculation: identical sub-trees share the same instance in memory. This compression allows the XDDs to represent efficiently the relationships between combinations of events (called configurations) and the corresponding execution times. A configuration γ ∈ Γ is the combination of activation or inactivation of events (Γ = ℘(E)) and corresponds to a path from the root node to a leaf in the XDD DAG.

When events are taken into account, the actual time for each vertex is represented by a map between event configurations and the corresponding times (i.e. in the domain Γ → Z # ) the size of which is combinatorial with respect to the number of events (which determines the cost in terms of computation time). XDDs efficiently solve this problem by factorizing identical sub-trees. In [START_REF] Bai | Improving the Performance of WCET Analysis in the Presence of Variable Latencies[END_REF], it has been shown that the subtree factorization frequently occurs in realistic benchmarks which largely speeds up the analysis. Yet, an isomorphism between XDD and Γ → Z # exists:

XDD α ↼ - -⇁ β (Γ → Z # )
. This means that XDD can be deemed as a lossless compression of the map (Γ → Z # ). In the remainder of the paper, we note f [γ] the time corresponding to configuration γ in f (for f ∈ XDD or f ∈ Γ → Z # since both are equivalent from a functional point of view).

In [START_REF] Bai | Improving the Performance of WCET Analysis in the Presence of Variable Latencies[END_REF], it was shown that any binary operation ⊙ on Z # used in (Γ → Z # ) can be transferred in the XDD domain in an equivalent operation such that performing the operation in the XDD domain is lossless:

∀s 1 , s 2 ∈ (Γ → Z # ) 2 , ∀γ ∈ Γ, s 1 [γ] ⊙ s 2 [γ] = (α(s 1 ) α(s 2 ))[γ] (3)
with α the morphism from (Γ → Z # ) to XDD. The operations used in XG are max and + (Eq. ( 1)). These two operations are transferred into the domain of XDD, respectively ⊕ and ⊗1 , such that the time corresponding to each configuration in the resulting XDD is exactly the time computed for each configuration without XDD:

∀s 1 , s 2 ∈ (Γ → Z # ) 2 , ∀γ ∈ Γ, s 1 [γ] + s 2 [γ] = (α(s 1 ) ⊗ α(s 2 ))[γ] max(s 1 [γ], s 2 [γ]) = (α(s 1 ) ⊕ α(s 2 ))[γ] (4)
The implementation of this operation is detailed in [START_REF] Bai | Improving the Performance of WCET Analysis in the Presence of Variable Latencies[END_REF]. Shortly, combines XDD operands along sub-trees and applies ⊙ when leaves need to be combined. Now, one can implant XDDs into the XG computation (Eq. ( 1)) by replacing max by ⊕ and + by ⊗. Each ρ in equation ( 1) now becomes a XDD recording all execution times with respect to the configurations of events. By doing that, we now compute all execution times in a single traversal of the XG. Let us consider some concrete examples in the computation of the XG showed in Figure 1 with XDDs. Three events are considered and highlighted in the figure: IC 0 , IC 1 and DC 2 . The IC events are instruction cache events, meaning that the associate instruction fetch may result in instruction cache miss, leading to an increased latency; DC 2 is a data cache event. The extra latency of both types of events is 5 cycles. Figure 2a The isomorphism guarantees that using an XDD to perform the XG analysis is precise by following the dependency resolution rule (Eq. ( 1)) and the proposed topological order. However, the graph can only be built for sequentially executed instructions which raises difficulties for the pipeline analysis at CFG level. Hence, the next section proposes a pipeline analysis in the paradigm of state machine which can be easily adapted for the analysis at CFG level and allows to leverage algebraic property of XDD to speed up the computation.

Configuration time IC 0 , IC 1 , DC 2 15 IC 0 , IC 1 , DC 2 15 IC 0 , IC 1 , DC 2 10 IC 0 , IC 1 , DC 2 10 IC 0 , IC 1 , DC 2 14 IC 0 , IC 1 , DC 2 9 IC 0 , IC 1 , DC 2 10 IC 0 , IC 1 , DC 2 5 (b) Explicit representation IC 0 4 9 ⊗ DC 0 1 6 = DC 0 IC 0 IC 0 5 10 15 (c) Example of ⊗ Fig. 2: Example of XDDs IV. RESOURCE BASED MODEL
The usual approach, that consists in building and solving an XG for each BB on its own, is no more sustainable when out-of-order bus accesses have to be supported. The bus access interactions can indeed span over BB bounds.

This section proposes to solve this issue by turning the original XG model into a state machine model where the pipeline analysis is performed by applying transitions on pipeline states. Moreover, by leveraging the algebraic property of XDDs, we improve the computational model by implementing transitions as products of matrices. The matrices can be pre-computed before the pipeline analysis.

A. Temporal State

The dependencies d ∈ D in the XG model the use of resources, such as pipeline stages, queues etc. For instance, in our 5-stage in-order pipeline, determining the start time of an instruction I i ∈ I * in stage DE requires:

ρ [Ii/DE] = ρ [Ii-1/DE] ⊕ ρ * [Ii-2/DE] ⊕ ρ * [Ii/F E] ⊕ ρ [Ii-2/EX] ρ * [Ii-2/DE] = ρ [Ii-2/DE] ⊗ λ [Ii-2/DE] ρ * [Ii/F E] = ρ [Ii/F E] ⊗ λ [Ii/F E]
This corresponds to the computation of Eq. ( 1) extended to the XDD domain: we use ⊕ instead of max and ⊗ instead of +. As in the integer case, each computation requires the results of the computations of previous instructions (e.g.

ρ [Ii/DE] requires ρ [Ii-1/DE] and ρ * [Ii-2/DE]
), which correspond to the release time of the concerned resources.

Table I shows the information required to compute the start time of any instruction I i in stage DE: it forms a vector of 6 elements, each element being an XDD. The vector depends on the structure of the pipeline, but an important point is that any architecture that can be described in the XG model can also be expressed as a vector of XDDs.

Such a vector can be similarly built for each instruction and each pipeline stage. Table II shows the complete dependency information to be maintained for each stage of our example pipeline. The symbol -∞ denotes the absence of dependency2 . I f etch , I load , I store and I Ri are, respectively, the last instructions that have fetched an instruction block from memory, performed a load, performed a store and wrote to register R i (in stage s Ri ).

Let D be the set of dependencies listed in Table II. The temporal state of the pipeline can be represented by a vector in the domain S = XDD |D| . For a given stage s, a temporal state ⃗ S ∈ S, and the set of dependencies D [Ii/s] ⊂ D applicable to XG vertex [I i /s], the start and end times of this vertex can now be rewritten as:

ρ [Ii/s] = d∈D [I i /s] ⃗ S[i d ] (5)
ρ * [Ii/s] =ρ [Ii/s] ⊗ λ [Ii/s] (6)
where i d denotes the index of dependency d within vector ⃗ S.

B. Pipeline Analysis with Temporal States

We now present how temporal states are updated during the analysis to account for the execution of instructions in the pipeline. To simplify the computation, we add an element ϱ at index i ϱ to the state vector. It records the current time all along the analysis: we refer to ϱ as the time pointer.

Definition IV.1. Following the principle of XG analysis, the behavior of an instruction in a pipeline stage can be broken down into four steps.

• Step 1. The instruction cannot be executed in the stage before all its dependencies are satisfied (Eq. ( 5)). This is modelled as follows. First, the time pointer is reset to 0 = LEAF (-∞) (Step 1.1). Then, each dependency time is accumulated with ⊕ into the time pointer (Step 1.2). At the end of Step 1, the time pointer records the maximum

[I i-1 /DE] ρ * [I i-2 /DE] ρ * [I i-1 /DE] ρ * [I i /F E] ρ [I i-2 /EX] ρ [I i-1 /EX]
[I i-1 /F E] ρ * [I i-1 /F E] ρ * [I i-2 /F E] -∞ ρ [I i-1 /DE] ρ [I i-2 /DE] DE ρ [I i-1 /DE] ρ * [I i-1 /DE] ρ * [I i-2 /DE] ρ * [I i /F E] ρ [I i-1 /EX] ρ [I i-2 /EX] EX ρ [I i-1 /EX] ρ * [I i-1 /EX] ρ * [I i-2 /EX] ρ * [I i /DE] ρ [I i-1 /M E] ρ [I i-2 /M E] ME ρ [I i-1 /CM ] ρ * [I i-1 /M E] ρ * [I i-2 /M E] ρ * [I i /EX] ρ [I i-1 /CM ] ρ [I i-2 /CM ] CM ρ [I i-1 /M E] ρ * [I i-1 /CM ] ρ * [I i-2 /CM ] ρ * [I i /M E] -∞ -∞ Fetch Order Memory Order Data Dependencies FE ρ * [I f etch /F E] -∞ -∞ DE -∞ -∞ -∞ EX -∞ -∞ ρ * [I R0 /s R0 ] ρ * [I R0 /s R1 ] ... ME -∞ ρ * [I load /M E ρ * [I store /M E] ρ * [I R0 /s R0 ] ρ * [I R1 /s R1 ] ... CM -∞ -∞ -∞
release time of all dependencies which is the actual start time for the analyzed XG vertex. The transitions for the temporal state are defined with the functions τ reset and τ wait :

τ reset : S → S, τ reset ( ⃗ S) = ⃗ S ′ | ⃗ S ′ [i] = ⃗ S[i] ⊗ 0 if i = i ϱ ⃗ S ′ [i] = ⃗ S[i] otherwise (7)
τ wait : N × S → S,

τ wait (x, ⃗ S) = ⃗ S ′ | ⃗ S ′ [i] = ⃗ S[i] ⊕ ⃗ S[x] if i = i ϱ ⃗ S ′ [i] = ⃗ S[i] otherwise (8)
τ wait has to be called for each dependency (with index x in the temporal state vector) of the current vertex. • Step 2. Some resources (e.g. the Queues between stages) are released at the start of an XG vertex. The corresponding dependencies (Queue Capacity) have to be updated with the start time ρ recorded by the time pointer ϱ.

Generally, the update of the vector is done with τ move :

τ move : N × N × S → S, τ move (i dest , i src , ⃗ S) = ⃗ S ′ | ⃗ S ′ [i] = ⃗ S[i src ] if i = i dest ⃗ S ′ [i] = ⃗ S[i] otherwise (9)
τ move copies a vector element into another element and overwrites the destination value. Updating the dependency of a single resource amounts to copying ϱ into the slot of the dependency: for example, updating the state of a dependency d of index i d with the start time (recorded in the time pointer ϱ) consists in τ move (i d , i ϱ , ⃗ S). The state of FIFO resources (like queues) requires updating several temporal state slots (i to i + n -1 with n the FIFO capacity) to express the shift of the n last FIFO uses. Hence FIFO resources are updated by a series of τ move on the n FIFO slots in the temporal state and by setting the first slot to ϱ, the use time for the first FIFO element:

∀j ∈ [i, i + n -2], τ move (j + 1, j, ⃗ S); τ move (i, i ϱ , ⃗ S
τ consume (λ [Ii/s] , ⃗ S) = ⃗ S ′ | ⃗ S ′ [i] = ⃗ S[i] ⊗ λ [Ii/s] if i = i ϱ ⃗ S ′ [i] = ⃗ S[i] otherwise (10)
• Step 4. The instruction finishes its execution and the dependencies recording the end time of the current vertex are updated. The τ move operation is used in the same way as in the Step 2.

As in the original XG resolution model, the computational model with temporal states has to follow the topological order so that the times recorded in the XDD vector refer to the correct timing of resources. In other words, if the state is correctly updated according to the rules stated above, the resource-based model is equivalent to the original XG analysis but expressed in state machine fashion. The implementation using XDDs extends the model to consider all possible cases according to the timing variations without any loss. The BB analysis is consequently exact with respect to the XG pipeline model.

C. The computational model

An important property of the XDD domain is that, equipped with ⊕ and ⊗, it forms the semiring ⟨XDD, ⊕, ⊗, 0, 1⟩ with 0 = LEAF (-∞) and 1 = LEAF (0). As the transition functions τ are affine in this domain, their application can be expressed as matrix multiplications. Combining and precomputing these matrices will help to speed up the pipeline analysis at CFG level since some BBs need to be recomputed several times in different execution contexts.

Scalar and matrix multiplication on XDD semiring is similar to the linear algebra over R by replacing + by ⊕, × by ⊗:

Definition IV.2. The scalar multiplication is defined by:

• : XDD N × XDD N → XDD, [f 0 , f 1 , ..., f N -1 ] • [f ′ 0 , f ′ 1 , ..., f ′ N -1 ] = 0≤i≤N -1 f i ⊗ f ′ i Definition IV.3.
The matrix multiplication is defined by:

• : XDD N ×M × XDD M ×L → XDD N ×L , B • C =   A i,j   |A i,j = 1≤k≤M B i,k ⊗ C k,j
Definition IV.4. The identity matrix Id on the XDD semiring is defined by:

Id =   A i,j   |A i,j = 1 if i = j 0 otherwise
Note that, by definition, ⃗ S • Id = ⃗ S: any matrix column at index i contains only 0 except for the row i that contains a 1, which maintains unchanged the value of ⃗ S[i] in the resulting vector. To implement the transition functions τ as matrix multiplications, the matrix Id is taken as a basis and only the cells that have an effect on the vector have to be changed.

1) A 0 on the diagonal of the Id matrix at the timer pointer position resets it: ⃗ S[i ϱ ] ⊗ 0 = 0:

τ reset ( ⃗ S) = ⃗ S • M reset = ⃗ S •   A i,j   |A i,j = 0 if i = j = i ϱ Id i,j otherwise (11)
2) For a given slot at index x in ⃗ S, τ wait (x, ⃗ S) is represented by a matrix M wait(x) with a 1 at position (x, i ϱ ) resulting in the operation ϱ ⊕ (1 ⊗ ⃗ S[x]):

τ wait (x, ⃗ S) = ⃗ S • M wait(x) = ⃗ S •   A ij   |A ij = 1 if i = i ϱ ∧ j = x Id ij otherwise (12)
3) τ move (i src , i dest , ⃗ S) is represented by a matrix M move(isrc,i dest ) where the element at (i dest , i dest ) is set to 0 and the element (i dest , i src ) to 1 s.t. element i dest in the result becomes

(0⊗ ⃗ S[i dest ])⊕(1⊗ ⃗ S[i src ]) = ⃗ S[i src ]. τ move (i src , i dest , ⃗ S) = ⃗ S • M move(isrc,i dest ) = ⃗ S •   A ij   |A ij =      0 if i = j = i dest 1 if i = i dest ∧ j = i src Id i,j otherwise (13)
4) For a given latency λ, τ consume (λ, ⃗ S) can be represented by a matrix M consume(λ) , obtained from Id by putting λ at position (i ϱ , i ϱ ).

τ consume (λ, ⃗ S) = ⃗ S • M λ consume = ⃗ S •   A ij   |A ij = λ if i = j = i ϱ Id i,j otherwise (14)
Theorem IV.1. Each transition function τ applied to the timing vector is a linear map from S to S Proof. Direct since we have already given the matrix representation of each transition in Definition IV.4.

Consequently, the operations performed at each step are also linear because they are combination of τ functions. Their matrix representation is simply the multiplication of each invoked τ function. For example,

M Step1[Ii/s] = M reset • d∈D [I i /s] M wait(i d )
with D [Ii/s] the set of dependencies required by [I i /s] and i d the index of resource d in the state vector.

Similarly, we can express M Step2[Ii/s] , M Step3[Ii/s] and M Step4[Ii/s] by invoking the corresponding τ functions. As each step is linear, the operation when analyzing one instruction on a stage is also linear because it is the combination of the 4 steps.

M [Ii/s] = M Step1[Ii/s] •M Step2[Ii/s] •M Step3[Ii/s] •M Step4[Ii/s]
Finally, the whole analysis of a BB a ∈ V is composed by the analysis of each instruction in each pipeline stage:

M a = Ii∈a s∈P M [Ii/s]
With a matrix such as M a , it is easy and fast to compute the output temporal state ⃗ S ′ ∈ S corresponding to an input temporal state ⃗ S ∈ S for a BB a:

⃗ S ′ = ⃗ S • M a (15)
V. PIPELINE ANALYSIS ON THE CFG This section extends the temporal state computational model, presented in the previous section, to the complete analysis of the CFG. It mainly consists in tracking the explicit set of possible temporal states for each BB all over the CFG execution paths.

A. Computing the context with Rebasing operation

In an analysis at BB-level, a temporal state contains times relative to the start of a BB. In an analysis at CFG-level, a temporal state should contains times relative to the start of the program and the temporal states should be tracked for all possible execution paths. This is generally infeasible because of the huge number of execution paths, especially in the presence of loops. Now the main reason for which we want to compute exact temporal states at CFG-level is to determine the exact timings of bus accesses. But these timings do not need to be absolute with respect to the start of the program. Instead, they can be relative to arbitrarily-chosen time bases, as long as XDDs with different bases are not mixed.

We call rebasing the operation that consists in changing the origin of the timeline of a temporal state. The temporal state at the end of BB a represents the delay induced by the execution of a to the start of the following BB b. Considering the start of b as a new time base T ∈ XDD, we can get a new temporal state relative to T by subtracting T from the times in the temporal state in the base of BB a. The outcome is a temporal state containing XDDs with positive or negative times relative to T . The relationship between times and events in the temporal state is preserved. The subtraction in XDDs ⊘ is built in the usual way from theoperator (Eq. ( 3)).

Rebasing a temporal state is lossless because ⊘ is reversible. By adding T (with ⊗), one can find back the state before rebasing. Rebasing is very helpful to reduce the size of XDDs in the temporal state: an event removed by rebasing has no effect on the following BBs but it does not mean it has no effect at all. Its contribution to the overall WCET is simply linear with respect to the number of occurrences of the BB. Intuitively, the execution of an instruction depends on the execution of nearby instructions. Thus the effect of events is generally short term and is, in practice, often eliminated by rebasing.

B. Generation of Events within loops

Each event computed by global analyses is linked to a particular instruction. The pipeline analysis of a BB presented so far deems the occurrence of events unique. This is not true when an event arises in a BB of a loop body, since it may occur or not in different iterations. We would get unsound timings if we denoted these different event occurrences with the same event node in the XDD. To fix this, a generation number is associated with each event. To prevent a blowup of temporal states, this generation number is relative to the current iteration and is incremented in the current temporal state each time the analysis iterates in the loop. The generation number thus distinguishes occurrences of an event in different iterations. Fortunately, this method does not result in an endless increase of generations because (a) the effect of events is often bounded in time and (b) the WCET calculation requires to bound the number of loop iterations.

C. The CFG pipeline analysis

Finally, the complete pipeline analysis is designed like a classical data-flow analysis with a work list. Each BB is associated with a set of input temporal states and a set of output temporal states (initially empty). The analysis starts with an initial temporal state at the entry of the CFG and propagates the new states all along the CFG paths. For each entry edge of a BB, the input state set is the union of the output states of the preceding BBs. Each input state is updated (i.e. multiplied by the pre-computed matrix) and rebased to make a new output state. If the set of its output states differs from the original set, the successors of the BB are pushed into the work list. The process is repeated until finding a fixpoint on all sets of input/output states has been reached. For readers familiar with abstract interpretation, this is actually the collecting semantics of our pipeline semantics.

Using XDD, the variability caused by events is efficiently recorded without any loss thanks to its compaction property. Besides, the analysis at CFG-level collects the set of all possible pipeline states, meaning it is also lossless according to the variability caused by the control-flow. In turn, this means that the resulting set of vectors of XDDs contains sufficient information to determine the exact temporal behavior of each BB in all possible situations. They can then be used to precisely analyze the temporal behavior in presence of outof-order scheduled resources.

VI. MODELING THE SHARED MEMORY BUS

In previous work, our analysis was valid only when all the resources were accessed in the program order. However, in embedded microprocessors, the instruction and data caches often share a common bus to the memory (or to a unified L2 cache). This introduces an out-of-order behavior: an instruction cache miss might access the shared bus before a data cache miss generated by an older instruction. In other words, the variability due to events in the start times of the FE and ME nodes may change the access order to the shared bus. Since XG dependencies are not expressive enough to model out-of-order bus allocations, we propose, in this section, an extension to the pipeline analysis to efficiently manage the shared bus accesses according to the different configurations of the temporal states. It supports the usual bus arbitration policy: first-come-first-served (FCFS), with priority given to the ME stage in case of simultaneous bus accesses.

A. Bus scheduling properties

Since we consider an in-order pipeline, the number of possible contention scenarios on the shared bus is limited. For instance, an instruction using the bus in the ME stage cannot contend with any subsequent instructions in the ME stage (load/store memory order is preserved). Similarly, bus accesses by the FE stage follow the program order. Moreover, the pipeline order ensures that a request emitted by an instruction in the FE stage is granted the bus before a request emitted by the same instruction in the ME stage. This means that the bus allocation in an in-order pipeline is almost completely in-order,

M E 0 , F E1, F E2, F E3 ρ M E 0 ≤ ρ F E 1 ρ M E 0 F E1, M E 0 , F E2, F E3 ρ F E 1 < ρ M E 0 ≤ ρ F E 2 max(ρ F E 1 + λ BU S , ρ M E 0 ) F E1, F E2, M E 0 , F E3 ρ F E 2 < ρ M E 0 ≤ ρ F E 3 max(ρ F E 2 + λ BU S , ρ M E 0 ) F E1, F E2, F E3, M E 0 ρ F E 3 < ρ M E 0 max(ρ F E 3 + λ BU S , ρ M E 0 )
with only one exception: a bus request in the ME stage by an instruction denoted M E 0 may be delayed by a bus request in the FE stage by a younger instruction denoted F E i|i>0 . To simplify the notation in this section, M E 0 and F E i|i>0 denote the instructions as well as the XG vertex (e.g. M E 0 also denotes vertex

[M E 0 /M E]; F E 1 also denotes [F E 1 /F E]).
In-between instructions are disregarded but are still accounted for in the matrices used to update the temporal states.

To sum up, F E i can delay M E 0 only if F E i is ready to enter FE stage before M E 0 is ready to enter ME. In the XG model, this situation can only happen when F E i does not depend on M E 0 , that is, when there is no path from M E 0 to F E i3 . In the example of Table III, we consider that M E 0 can only be delayed by F E 1 , F E 2 and F E 3 . For a particular configuration of events, there are four possible schedules that are shown in the first column of the table. These four schedules correspond to the four possible ways to interleave M E 0 with F E i accesses. The actual schedule is determined by comparing the ready time of M E 0 (ρ M E0 ) with the ready times of F E 1 , F E 2 and F E 3 (resp. ρ F E1 , ρ F E2 and ρ F E3 ): the second column shows the condition corresponding to each schedule. The third column gives the actual time at which M E 0 gets the bus with λ BU S denoting the latency of a bus access (including the memory transaction): if M E 0 is the first to be ready, then it gets the bus at time ρ M E0 . Otherwise, M E 0 gets the bus at the maximum time between its ready time and the release time of bus by the F E i contender.

B. Batch bus scheduling with XDD

Table III shows the schedule of M E 0 for a given configuration. However, when times are expressed as XDDs, a particular XDD may support configurations with different bus schedules. That said, we must extend the computation of the condition and the scheduling time in order to support XDDs. Figure 3 shows such an example in a simpler scenario: M E 0 may be delayed by F E 1 and F E 2 . Let us assume their start date without counting the contention (ρ Si ) as shown in the figure . The objective is to compute the actual start dates of M E 0 and F E i with contention (ρ M E0 and ρF Ei ). The instruction fetch in F E 1 may result in a cache hit or a cache miss, which is represented by event ic 1 . The instruction fetch in F E 2 is assumed to be classified as Always Miss, meaning that it always requests the bus. The latency of a bus access is assumed to be 9 cycles. The events e 0 and e 1 are events related to the instructions before M E 0 that are assumed to impact the start time of M E 0 and F E 2 .

XDD (a) shows the ready time of M E 0 and (b) the initial value of ρME0 -the scheduling time of M E 0 on the bus (+∞ means that no access is yet scheduled). (c) shows the initial value of ρ rel , recording the release time of the bus by F E i (-∞ denotes that the bus is not used by any F E i for now).

The ready time of F E 1 (d) is computed from the initial state ⃗ S 0 and the matrix between M E 0 and F E 1 . The event ic 1 indicates with -∞ the configuration where F E 1 does not use the bus (hence it is not concerned by the contention).

ρ M E0 (a) and ρ F E1 (d) are compared using ◀ M E to get the configurations and the time ( ρ schedM E0 (e)) when M E 0 takes the bus, i.e. is scheduled, before F E 1 (◀ M E is formally defined in Eq. ( 16)). Other configurations are assigned +∞, denoting that they are not processed yet. Notice that a -∞ configuration in ρ F Ei does not allow M E 0 to be scheduled as subsequent F E j>i might allocate the bus before M E 0 . ρ schedM E0 is then used to update ρME0 using the minimum operator ⊖ (f).

ρ schedF E1 (g), i.e. the configurations where F E 1 gets the bus, is computed in a similar way as ρ schedM E0 but with operator ◀ F E that selects the configurations in which F E gets the bus, using the strict < comparison instead of ≤ because the M E stage has priority over the F E stage in case of simultaneous requests. By adding the latency of the bus (λ BU S ) to ρ schedF E1 , we are able to update, using ⊕, the release time of the bus after F E 1 (ρ rel (h)). Finally, we compute the actual schedule of F E 1 (ρ F E1 (i)) that is the time of ρ schedF E1 if F E 1 is scheduled, or otherwise the release time of the bus by M E 0 (ρ M E0 ⊗ λ BU S ). Now, as the actual schedule of F E 1 is known, the release time of the bus at F E 1 is computed and is used to adjust the temporal state. By multiplying the state ⃗ S F E1 by the matrix M F E1-F E2 , we get the ready time of F E 2 (j). In the second iteration, first, ρ M E0 (a) is compared with ρ F E2 (j) with the operator ◀ M E . The actual scheduling time ρ schedM E0 (k) is computed by considering the maximum between ρ schedM E0 and the release time of the bus by F E 1 (ρ rel ) according to the third column of Table III. Then, ρME0 is updated (l). The schedule of F E 2ρ schedF E2 (m) is computed with the operator ◀ F E applied to ρ F E2 and ρ M E0 which is then used to update the release time of the bus ρ rel (n). The actual schedule of F E 2 is computed with respect to the use of the bus by M E 0 (o).

When the end of the sequence is reached, there are no further subsequent instructions that may contend with M E 0 and the remaining +∞ in ρME0 represents configurations accessing the bus after F E 1 and F E 2 . They are replaced by the maximum between the ready time of M E 0 and the release times of the bus by F E 1 and F E 2 , ρ rel .

ρ Si ρ schedM E0 = (ρ M E0 ◀ M E ρ F Ei ) ⊕ρ rel ρME0 = ρME0 ⊖ ρ schedM E0 ρ schedF Ei = ρ F Ei ◀ F E ρ M E0 ρ rel ρF Ei M E 0 F E 1 F E 2 e 0 e 1 1 3 15 (a) +∞ (b) -∞ (c) ic 1 -∞ 2 (d)
Operator ◀ M E (resp. ◀ F E ) has a straightforward definition, setting to +∞ the configurations where M E (resp. F E) does not get the bus:

∀f M E , f F E ∈ XDD 2 , ∀γ ∈ Γ, (f M E ◀ M E f F E )[γ] = f M E [γ] if f M E [γ] ≤ f F E [γ], +∞ otherwise
(f F E ◀ F E f M E )[γ] = f F E [γ] if f F E [γ] < f M E [γ],
+∞ otherwise (16) All these calculations seem a bit complex but it must be kept in mind that real XDDs are much more complex with much more configurations and relying on the XDD operators allows to benefit from the XDDs optimizations.

C. Contention Analysis

The contention analysis depicted in the previous example is described more formally in this paragraph. Basically, the pipeline analysis is extended by splitting the BBs at contention points, i.e. at the XG nodes where a bus access may occur (M E or F E stages causing cache misses). Then they are grouped in a sequence of one M E access followed by zero or several F E accesses, (M E 0 , F E 0<i≤n ). The instructions between two successive contention points are summarized by a pre-computed matrix.

Algorithm 1 is then applied to compute the possible interleaving of bus accesses for all configurations of the sequence (M E 0 , F E 0<i≤n ). Additionally, it takes as input the temporal state ⃗ S 0 . The result is the definitive schedule of M E 0 (i.e. ρME0 ) and of F E i (i.e. ρF Ei ).

Algorithm 1: Contention computation.

Input: ⃗ S 0 ∈ S, (M E 0 , F E 1≤i≤n ) Output: (ρ M E0 , ρF E 1≤i≤n ) 1 ρME0 = LEAF(+∞) 2 ρ rel := LEAF(-∞) 3 ⃗ S F E1 := ⃗ S M E0 • M M E0-F E1 4 i := 1; 5 ρ M E0 := ⃗ S 0 [i ρ ] 6 while i ≤ n ∧ (∃γ ∈ Γ ∧ ρME0 [γ] = +∞) do 7 if F E i .mustU seBus() then 8 ρ F Ei := ⃗ S F Ei [i F E ] 9 else 10 ρ F Ei := ⃗ S F Ei [i F E ] ⊗ NODE(ic i , -∞, 0) 11 ρ schedM E0 := (ρ M E0 ◀ M E ρ F Ei ) ⊕ ρ rel 12 ρME0 := ρME0 ⊖ ρ schedM E0 13
ρ schedF Ei := ρ F Ei ◀ F E ρ M E0 14
ρ rel := ρ rel ⊕ (ρ schedF Ei ⊗ λ BU S ) 15 ρF Ei := ρ schedF Ei ⊖ (ρ M E0 ⊗ λ M E0 ) 16 ⃗ S F Ei+1 := ( ⃗ S F Ei ⊕ [0, ..., 0, ρF Ei ⊗ λ BU S ]) • M F Ei-F Ei+1 17 i = i + 1 18 ρME0 := ρME0 ⊖ (ρ rel ⊕ ρ M E0 )
Initially, M E 0 is considered as not scheduled whatever the considered configuration and ρME0 is set to LEAF (+∞) (line 1). It will then be updated after considering the contention with each subsequent F E i . When M E 0 does not contain +∞ anymore or when all F E i have been processed, the schedule of M E 0 is complete (condition at line 6). Line 2 initializes ρ rel that records the release time of the bus by F E i to -∞ as no F E i has been processed yet.

In line 3, the temporal state just before F E 1 is computed by applying the matrix M M E0-F E1 to the initial state ⃗ S 0 ; i is initialized in line 4 and will range over the Contention Points, 1 to n. The ready time of M E 0 is recorded into ρ M E0 at line 5. Lines 7-10 compute the ready time of F E i if the access always or sometimes results in a miss (according to mustU seBus()). The latter case is expressed by the event ic i and by adding the NODE(ic i , -∞, 0) to ρ F Ei : -∞ denotes the case where ic i does not arise and there is no bus access.

ρ schedM E0 , M E 0 configurations getting the bus before F E i , is computed with ◀ M E at line 11 by comparing the ready times of M E 0 with the ones of F E i . According to the last column of Table III, these configurations are fixed by taking the maximum between the ready time of M E 0 and the release time of the bus ρ rel . The schedule of M E 0 at this iteration is accumulated in the definitive schedule of M E 0 at line 12. At line 13, the schedule of F E i is computed. Notice that as the ready time of F E i contains -∞ to denote the case where it does not use the bus, these -∞ are kept in ρ schedF Ei . By adding the bus latency λ BU S to ρ schedF Ei and then ⊕ with ρ rel , the release time of the bus is only updated for configurations γ where F E i uses and gets the bus (ρ schedF Ei [γ] ̸ = +∞) (line 14). Notice that the +∞ in ρ rel cannot overwrite the release time of the bus by F E i because F E i cannot get the bus if any prior F E j<i does not get the bus. At line 15, the actual schedule of F E i is computed by replacing the +∞ in ρ schedF Ei (where F E i loses contention in favor of M E 0 ) by the release time of the bus by M E 0 . Configurations where time is +∞ in ρ schedF Ei must not be +∞ in ρME0 because only one of F E i or M E 0 is scheduled. However, as ρ schedF Ei configurations not leading to +∞ are lower than ρME0 (otherwise it is considered as non-scheduled), ⊖ can be used to implement the replacement.

At line 16, the temporal state is updated regarding the schedules of F E i , by applying ⊕ between the time pointer of the state vector and the release time of the bus by F E i . The updated state is then multiplied by matrix M F Ei-F Ei+1 to obtain the ready time of F E i+1 . Line 18 takes into account the remaining +∞ configurations in ρME0 that are not already scheduled by the loop. The times assigned to these configurations are the maximum between the ready time of M E 0 and the bus release time by F E i . Notice that +∞ in the ρME0 may also be caused by the fact that none of the F E i have used the bus: this time is recorded as -∞ in ρ rel and is hence automatically overwritten by the ready time of M E 0 .

VII. EVALUATION

The performance of the analysis strongly depends on the size of the XDDs in the pipeline states and on the number of pipeline states. Both metrics are related to some inherent properties of the analyzed program and of the microarchitecture, the impact of which is difficult to theoretically estimate. Therefore, we experiment our analysis on realistic benchmarks that empirically provide a better understanding of the performance.

A. Experimental Setup

The pipeline used in the examples of the previous sections was chosen to enhance the readability of the article. For the experimentation, we consider a more powerful microarchitecture with more parallelism leading to more complex temporal states. In addition, this new pipeline allows demonstrating the scalability of our approach.

Our pipeline has 4 stages (FE, DE, EX, CM), each able to process 4 instructions per cycle. In the FE stage, it fetches instructions from a single-level instruction cache. The FE stage is able to fetch 4 instructions of the same memory block simultaneously, with a latency of 7 cycles in case of a cache miss (ignoring possible contention). The DE stage decodes the instructions and the EX stage handles all arithmetic, floating point and memory related operations in several functional units (FU). Four ALUs (Arithmetic and Logic Units) are available and can be simultaneously used by independent instructions. The latency of arithmetic operations is 1 cycle for additions and subtractions, 2 cycles for multiplications and 7 cycles for divisions. One FPU (Floating Point Unit) is available with a latency of 3 cycles for additions and subtractions, 5 cycles for multiplications and 12 cycles for divisions. A single MU (Memory Unit) handles memory-related operations (loads and stores). In case of a multiple load/store operation, the memory accesses are performed in order, and if one multiple load/store needs to use the memory bus (in case of data cache misses), it occupies it until all loads/stores are completed. The latency of data accesses is the same as for instruction fetches. In the EX stage, an issue buffer distributes the instructions to the appropriate FUs. Instructions using the same FU are executed in order; instructions using different FUs can be executed outof-order (if the absence of data dependencies).

The instruction cache is a 16-KByte 2-way set associative LRU (Least Recent Used) cache. The data cache is a 8-KByte 2-way set associative LRU cache. There is a single level of caches and they share the same bus to the main memory. We believe that this architecture is representative of many midrange processors used in real-time embedded systems.

The whole CFG analysis is implemented using the OTAWA toolbox [START_REF] Ballabriga | Otawa: An open toolbox for adaptive wcet analysis[END_REF]. Global analyses, including instruction and data cache analyses as well as control flow analyses are provided by OTAWA. The benchmarks are taken from the TACLe suite [START_REF] Falk | Taclebench: A benchmark collection to support worst-case execution time research[END_REF] compiled for the armv7 instruction set with a hard floating point unit. Among 79 tasks to be analyzed, 5 fail due to limitations in OTAWA (unsupported irregular control flow 4 , e.g. unable to solve dynamic branch address) and another 5 have been dropped due to the lack of annotations on the bounds of recursive function calls 5 , for which the WCET computation impossible.

B. Number of Temporal States

The first experiment explores the number of temporal states along the edges of BBs (representing the output of the source BBs and the input of sink BBs). The experimental results are shown in Figure 4. The x-axis shows the number of pipeline states and the y-axis shows the number of edges for each amount of states (in a logarithmic scale). The bars accumulate data from all the benchmarks.

The risk, with our approach at CFG level, is to face an exploding number of states which is a common concern of collecting semantic based analyses. Fortunately, the experimentation shows that most of the edges have less than 20 output states. This means that most of the timing variations due to events are efficiently represented in the XDDs of the temporal states. As expected, the XDDs successfully prevent the state explosion and keep the pipeline analysis tractable at CFG-level. The presence of some rare cases where the number of states is much higher is not blocking as the analysis time remains reasonable in most cases (cf. Section VII-D).

C. Events Lifetime

The second experiment measures the lifetime of events during the analysis. The longer the lifetime of events, the larger the complexity of the analysis in terms of number of states and size of XDDs. In our micro-architecture, an event is created by a cache access and may disappear from the XDD during the analysis, for two reasons: (i) it is absorbed by the pipeline: for example, when an instruction stalls in the EX stage due to a data cache miss, the next instructions may still be processed in the pipeline, completely hiding the stalling time -this event will stay alive only in a short time window during the analysis of other instructions executed in parallel. (ii) The events are stabilized and disappear thanks to the rebasing operation. Intuitively, we assume that in most situations, the events raised by an instruction only impact nearby instructions. Therefore, the lifetime of events provides a fine estimation of both the size of XDDs and the number of pipeline states of our analysis at CFG-level. As complement, in [START_REF] Bai | Improving the Performance of WCET Analysis in the Presence of Variable Latencies[END_REF], we provide detailed discussion and experiments, on different micro-architecture setups, of the size of XDDs for BB-level analysis where the pipeline absorption effect is the primary factor.

However, the pipeline analysis is only able to provide the lifetime information at the granularity of contention points because the effect of executing instructions between contention points is expressed by matrices. As collecting these statistics at a finer granularity would have an important adverse effect on the analysis time, we survey the liveness of events on this basis. Events are deemed as dead at contention points if the temporal state of which does not contain the event in any XDD contained in the vector. Thus, the lifetime statistics are overestimated by the number of instructions between contention points. Besides, the pipeline states are only rebased at the end of BBs so the lifetime of events in the middle of BBs does not consider the potential death due to rebasing. In the end, the measured lifetime in this experimentation is an over-estimation of the actual lifetime of events.

Figure 5 shows the experimental results. The x-axis is the lifetime of events (in instructions with limitations described above) and the y-axis, in logarithm scale, shows the number of events having this lifetime. These are also accumulated from the whole set of TACLe benchmarks. The statistics show that most events have a short lifetime (below 50 instructions). We have observed a unique lifetime of 602 instructions that is not represented to keep the figure readable. It turns out that in most situations where the lifetime is greater than 50, the events are in a very long BB. In the extreme case of the 602-instruction event lifetime, the involved BB contains 617 instructions (in benchmark md5) and the reported lifetime is an effect of the granularity level. Despite this very infrequent case, most events have short lifetimes and the size of temporal states (sum of XDDs sizes of the vector) is reasonable and the analysis remains efficient.

D. Analysis time

The analysis time includes the time to pre-compute the matrices and the duration of the pipeline analysis on the CFG. We run the analysis on a virtual machine on a cloud server with 8 GB RAM and 4-core Intel Broadwell processors. Only 2 cores are occupied simultaneously to process the benchmarks. We also measure the analysis time without leveraging the algebraic property of XDD to pre-compute the matrices (with a timeout of 1 hour) in order to clarify the benefit of this optimization. The results are shown in Figure 6. The xaxis shows the benchmarks and the y-axis plots the analysis time in seconds in a logarithmic scale. The analysis time with matrices is shown as green bars. At worst, the analysis with matrices finishes in 553s (9m13s). In most cases, it finishes in about 1 to 20s. In contrast, the analysis without matrices has both memory usage and speed issues as shown by the red (crashed because out of 8G RAM) and yellow bars (timeout after 1 hour). For those finishing within 1 hour (blue bars), the matrix optimization brings 217% speedup in average 6 . The rare cases where the analysis without matrix is faster are simple benchmarks where the cost of computing the matrices is not balanced by the speed-up. This result reveals that the pre-computation of matrices effectively reduces intermediate redundant computations, which enhances the analysis performance in terms of speed and memory usage. The analysis is still able to handle problematic cases (those that have a large number of temporal states or long lifetime events) in a reasonable time. Moreover, we observe that the industry-like applications encompassed in the TACLeBench collection (Debbie and Papabench) are analyzed in short times (respectively 10 and 15 minutes, summing the analysis times of all their tasks). Therefore, we believe that our approach could be used in industrial real-time applications (for example, Airbus requires at most 48 hours between the detection of a bug and the distribution of the fix, including temporal verification).

E. Precision

The presence of out-of-order resources enables potential timing anomalies [START_REF] Wenzel | Principles of timing anomalies in superscalar processors[END_REF]. This means that the pipeline analysis can not assume the local worst case to be the global worst case upon timing variations. In the presence of possible timing anomalies, a trade-off between precision and performance is more difficult to achieve: the analysis either has to track exactly all possible timing states or to cover the timing variations with a safe but largely over-estimated cost. In the example of the shared bus, the cost for not tracking precise pipeline states is to cover the latency of memory access with an upper bound by considering the maximal potential contention with prior and subsequent instructions. To evaluate this over-estimation, we implemented this strategy in etime, the state-of-the-art pipeline 6 average speed up = the sum of the analysis times of all the benchmarks without matrix divided by the sum of analysis times with matrices. analysis of OTAWA. We compare the WCET estimated with etime to the one estimated with the new approach.

Concretely, the etime analysis implements the same pipeline model (i.e. XG based) except for it does not use XDDs and considers the WCET of BBs locally instead of at CFG-level. In order to tighten the WCET, it considers all the combinations of events for each BB. But since it disregards the execution context, it may choose to drop the context at any time to reduce the exponential number of pipeline states -which is not safe with timing anomalies. Moreover, etime generates only one execution time for each BB (the worst one), while the new pipeline analysis provides all the possible execution times to the IPET stage. The way IPET can handle these multiple execution times has been detailed in [START_REF] Bai | A framework for calculating wcet based on execution decision diagrams[END_REF] and is out of the scope of this paper, but it clearly benefits the new approach. Finally, as etime originally did not support out-oforder accesses, we created a new type of event with a latency of one memory access that is associated to each memory access not classified as Always Hit or Always Miss in order to cover the waiting time of the shared bus.

As both etime and the approach presented in this paper are implemented with OTAWA, we are able to ensure that the micro-architectural model and global analyses are the same. Disregarding the safety issue due to ignoring timing anomalies, we believe that the WCET obtained by etime can be used as a reference of a classical static WCET approach that considers out-of-order resources without tracking exact pipeline states.

The experimental results are shown in Figure 7, in which the x-axis shows the benchmarks and the y-axis shows the gain in precision computed by (t etime -t new )/t etime , where t etime is the WCET obtained by etime and t new is the WCET obtained by our new approach. Due to the limited performance of etime, the epic benchmark does not finish within 6 hours. The susan benchmark also fails due to a bug in OTAWA. This is why the bars for these two benchmarks miss in the figure .  The experimental results show that, for most of the benchmarks, the WCET obtained by using the new approach is improved by 40% to 80%. In some rare cases (fft, two tasks of papabench, rad2deg, rijndael enc, rijndael dec and statemate), the gain is smaller but still around 20%-40%: these benchmarks are the least memory-intensive and get the worst results from global analyses, which explains why the overestimation on memory latency and the improved IPET (see [START_REF] Bai | A framework for calculating wcet based on execution decision diagrams[END_REF]) have a lower impact. This impressive improvement on the final WCET is explained by the precise estimation of the bus latency, the benefits of which are amplified by the improved IPET formulation. Concerning the latency of memory accesses, the new approach computes the exact waiting time. If we consider that the actual waiting time is low (which is the case in the example micro-architecture that is almost in-order), the worst memory latency accounted in etime is nearly doubled. The improved IPET applied to the new approach also contributes to the improvement: according to our experiments in [START_REF] Bai | A framework for calculating wcet based on execution decision diagrams[END_REF] it achieves itself 0%-50% of the gain precision depending on the benchmark. Moreover, the over-estimation on the pipeline analysis is even amplified by standard IPET (as opposed to our improved version [START_REF] Bai | A framework for calculating wcet based on execution decision diagrams[END_REF]) because the WCET of each BB is multiplied by the BB's execution count. This explains the impressive improvement up to 80% observed in Figure 7.

VIII. CONCLUSION

In this paper, we formally define an efficient state representation for pipeline timing analysis using vectors of XDDs. It enables the analysis of the pipeline at CFG-level. By leveraging the algebraic properties of XDDs, we perform the analysis as a sequence of matrix multiplications, which significantly reduces the analysis time. This analysis also improves the precision of the estimated WCET by 20% to 80% on the TACLe benchmarks compared to previous analysis implemented in the OTAWA toolset. We extend our new analysis to precisely take into account the contention on the memory bus shared by the instruction and data caches. This makes the analysis sound for timing-anomaly-prone processors. The measured analysis time for the TACLe benchmarks shows that the approach is scalable and should be practical for industrial applications.

As future work, we could benefit from the exact tracking of the temporal states to qualify more precisely the effects of timing variations in different micro-architectures. This could be used to eventually qualify good or bad micro-architecture designs in terms of predictability. This may also help to find better trade-offs in the design of time-predictable pipelines and alleviate over-stringent constraints on the pipeline such as strict-in-order execution, that often limits the performance of the processor. We also plan to extend our approach to all kinds of out-of-order scheduled resources. Although our operators and matrices calculation are correct whatever the out-of-order resource, the generalization of the contention model will likely raise performance issues as one can no longer leverage the constraints on the contention upon concurrent accesses. That said, we must find a scalable model of the interleaving of resource acquisitions when multiple out-of-order resources are involved.

TABLE IV: List of symbols and their signification

  shows the use of ⊕ when computing the start date of [I 4 /EX] where the first operand is the start date of [I 3 /EX] and the second operand is the end date of [I 4 /DE]. Figure 2b shows the explicit representation of the resulting XDD in Figure 2a. Figure 2c shows the use of ⊗ when computing the end time ρ * of [I 2 /M E]: the first operand is the start time and the second operand is the latency of [I 2 /M E].

•

  the start time of the previous instruction in stage DE: ρ [Ii-1/DE] -the Program Order dependency due to the use of DE stage in program order, • the end time of the second last instruction in stage DE: ρ * [Ii-2/DE] -the Capacity Order dependency due to the use of DE stage with limited capacity, • the end time of I i in stage F E: ρ * [Ii/F E] -the Pipeline Order dependency due to the use of the pipeline, • the start time of the second last instruction in stage EX: ρ [Ii-2/EX] -the Queue Capacity dependency due to the use of the queue between DE and EX with limited capacity. where I i-n represents the n th previous instruction. ρ [Ii/s] and ρ * [Ii/s] respectively stand for the start and the end time of vertex [I i /s]. The actual start time of I i in DE is the earliest date at which all dependencies are satisfied:

•

  ); Step 3. The started instruction spends λ [Ii/s] cycles in the stage. After this step, the value the time pointer is the end time of [I i /s]. τ consume : N × S → S,

Fig. 3 :

 3 Fig. 3: Batch bus scheduling with XDDs.

Fig. 4 :

 4 Fig. 4: The distribution of number of pipeline states. C. Events Lifetime

Fig. 5 :

 5 Fig. 5: The distribution of events lifetime.

Fig. 6 :

 6 Fig.6: The analysis time.

Fig. 7 :

 7 Fig. 7: WCET comparison

  ρ[i, st] the start time of an instruction i in a pipeline stage st ρ * [i, st] the end time of an instruction i in a pipeline stage st λv the latency of an instruction executed in stage v Z # Z ∪ {+∞, -∞} γ ∈ Γ one of the set of configurations of events α function converting Γ → Z # to XDD I i ∈ I the i th instruction of a sequence of instructions s ∈ P one stage of the set of pipeline stages d ∈ D [I/s] one dependency of the set of dependencies of [I/s] ⃗ S ∈ S one pipeline state vector of the set of pipeline states ϱ the time pointer of pipeline state ρ the definitive time of acquiring the bus

  The slanted solid edges model the Data Dependencies

	• The vertical dotted edges model the parallel execution of
	instructions in the superscalar stages (Program Order).
	• The vertical solid bent edges model the width of the
	stages -2 instructions per cycle (Capacity Order).
	• The slanted dotted edges model the capacity of FIFO
	queues (2 instructions) between stages (Queue Capacity).

•

TABLE I :

 I Information needed to determine the start time of any I i in stage DE

	Program Order	Capacity Order	Pipeline Order	Queue Capacity
	ρ

TABLE II :

 II The temporal state

		Prog. Order	Capacity Order	Pipeline Order	Queue Capacity
	FE	ρ

TABLE III :

 III Possible schedules of M E 0 with subsequent F Es.

	Schedule	Condition	Scheduling time of M E 0

It must be emphasized that the name of the transferred operators is not related to the original operator: ⊕ does not correspond to + but max, and it is ⊗ that corresponds to +, this is due to the algebra property of XDD semi-ring that we will mention later in section IV-C.

-∞ is convenient as it is neutral for the max operation.

The occurrence of such situations is limited by the size of the inter-stage queues in the pipeline.

pm, mpeg2, gsm enc, ammunition, rosace

recursion, huf f enc, quicksort, bitonic, anagram