  Worst-Case Execution Time (WCET) is a key component for the verification of
critical real-time applications. Yet, even the simplest microprocessors
implement pipelines with concurrently-accessed resources, such as the memory
bus shared by fetch and memory stages. Although their in-order pipelines are,
by nature, very deterministic, the bus can cause out-of-order accesses to the
memory and, therefore, timing anomalies: local timing effects that can have
global effects but that cannot be easily composed to estimate the global WCET.
To cope with this situation, WCET analyses have to generate important
over-estimations in order to preserve safety of the computed times or have to
explicitly track all possible executions. In the latter case, the presence of
out-of-order behavior leads to a combinatorial blowup of the number of pipeline
states for which efficient state abstractions are difficult to design. This
paper proposes instead a compact and exact representation of the timings in the
pipeline, using eXecution Decision Diagram (XDD) [1]. We show how XDD can be
used to model pipeline states all along the execution paths by leveraging the
algebraic properties of XDD. This computational model allows to compute the
exact temporal behavior at control flow graph level and is amenable to
efficiently and precisely support WCET calculation in presence of out-of-order
bus accesses. This model is finally experimented on the TACLe benchmark suite
and we observe good performance making this approach appropriate for industrial
applications.
