# WCET Analysis Based on Micro-Architecture Modeling for Embedded System Security
## 3 Design
### Pipeline Analysis  
The purpose of pipeline analysis is to comprehensively consider the effects of both the cache model and branch prediction, and to calculate the execution time for a basic block. Ref. [23] analyzes the impact of out-of-order execution pipelines on program execution time, noting that the execution time cannot be simply represented by the longest path of instruction execution; dependencies between instructions must also be considered. This paper achieves this by analyzing the commonly used five-stage pipeline architecture in ARMv8 processors: Instruction Fetch (IF), Decode (ID), Instruction Execute (EX), Memory Access (MEM), and Write Back (WB). We use execution graphs to model and analyze the pipelines of out-of-order executions. Execution graphs illustrate the dependencies between instructions using directed edges as follows:  
* The dependency between different stages of the same instruction. The completion of the previous stage is required before proceeding to the next stage.
* The dependency between different instructions in the same pipeline stages. Earlier instructions in the program have a higher priority.
* The data dependency between instructions.
* Queuing for idle Instruction Fetch Buffers (I-buffers) and Reorder Buffers (ROB).  
Assuming the size of the Instruction I-buffer is 2 and the size of the Reorder ROB is 4, a program and its corresponding execution graph is shown in Figure 7. The edge \(WB\to EX\) represents the data dependency between instructions, \(ID\to IF\) and \(MEM\to ID\) represent the dependencies between instructions due to the sizes of the I-buffer and ROB, respectively, and the dashed line \(EX\to EX\) indicates instructions competing for the same functional unit.  
Figure 6: CCG with virtual nodes.  
Since the analysis of the cache is performed using the CCG, the cache is ignored when establishing execution graphs; we assume that all instructions hit the cache. However, errors in branch prediction can cause the instruction pipeline to prefetch instructions along an incorrect path. To address this, we add instructions with the same size as the Reorder Buffer (ROB) along the erroneous path after the mispredicted branch instruction in the execution graph.  
For a node in execution phase, its earliest finish time and latest finish time can be obtained using Algorithm 1. \(earliest[t_{i}^{start}]\) denotes the earliest start time of node \(i\), \(earliest[t_{i}^{finish}]\) denotes the earliest finish time, \(latest[t_{i}^{start}]\) denotes the latest start time, and \(latest[t_{i}^{finish}]\) denotes the latest finish time. The latest finishing time of the last node is the estimated WCET. The functions in the algorithm are:  
* \(LatestTimes(G)\) calculates the latest ready, start, and finish times for the nodes. The latest start time depends on its latest ready time, which depends on the latest finish time of its predecessor or competitors. If a competitor has a lower priority than the instruction in question, the competitor will be excluded, and those whose execution times do not overlap will also be excluded. If a competitor has a higher priority than the instruction, it is assumed that all nodes preceding this competitor will delay the node. Once a node's latest start time is obtained, the latest ready times of its successor nodes are updated.
* \(EarliestTimes(G)\) calculates the earliest ready, start, and finish times of nodes. Unlike \(LatestTimes(G)\), the calculation of these times only considers competitors that conflict with the node's preparation time and hardware resources.  
```
Data:\(step=0\) foreach node \(i\) in \(G\)do \(earliest[t_{i}^{start}]\gets 0;earliest[t_{i}^{finish}]\leftarrow\infty\); \(latest[t_{i}^{start}]\leftarrow\infty\); \(latest[t_{i}^{finish}]\gets MIN\_LATENCY_{i}\);  end while while\(step<0\)do \(LatestTimes(G)\); \(EarliestTimes(G)\); \(step\gets step+1\);  end while Result:\(WCET=latest[t_{sink}^{finish}]\);
```  
**Algorithm 1**Basic Block WCET Analysis Algorithm  
Figure 7: ARM assembly and its execution graph.