# WCET Analysis Based on Micro-Architecture Modeling for Embedded System Security
## 4 Implementation
For example, if the instruction fetch buffer size is 2 and the instruction reorder buffer size is 4, then before the execution of a basic block, there will be 5 instructions waiting in the pipeline and one instruction being executed. Instructions in the cache may have dependencies on nearby instructions. Instructions that have dependencies on the previous basic block are referred to as the prologue, while those with dependencies on the subsequent basic block are called the epilogue. By using the functions \(collect\_prologs\) and \(collect\_epilogs\) to traverse paths in the CFG, we can establish the context between cache basic blocks. This allows us to account for dependencies within the contextual environment when analyzing the execution graph. In the implementation of the pipeline analysis, the function \(est\_units\) calculates the execution time of each basic block in the CFG. The function \(ctx\_unit\_time\) analyzes paths within the CFG, focusing on branch prediction and the contextual environment of the basic blocks. The function \(create\_egraph\) establishes the execution graph for each basic block, while the function \(est\_egraph\) applies Algorithm 1 to derive the final WCET target equation. IPET solves problems using ILP. The overall construction process for the ILP problem is shown in Figure 8. There are two branches related to branch prediction: the function after the first branch prediction extracts constraints related to branch prediction, while the function after the second branch extracts constraints related to the erroneous path prefetching strategy. The roles of the other functions are as follows:  
* \(cost\_func\) generates linear target equations based on the micro-architecture configured by the user. For scenarios involving branch prediction execution, \(cost\_term(BP\_CPRED)\) or \(cost\_term(BP\_MPRED)\) is invoked to construct target equations for correct branch prediction or branch prediction errors, respectively. \(mpcost\_func\) is invoked to establish the target Equation (15) to consider branch prediction and the instruction cache, along with their interactions. * \(tcfg\_cons\) generates constraints derived from the control flow information. * \(bf\_cons\) generates constraints derived from the branch prediction. * \(cache\_cons\) and \(mp\_cache\_cons\) generates constraints for cache hits or misses, as well as for constraints, when executing along erroneous paths. * \(user\_cons\) reads user-input constraint files and parses the linear constraint for the ILP problem. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Data Type** & **Name** & **Description** \\ \hline \(tcfg\_node\_t^{*}\) & \(bbi\) & Basic node pointed to. \\ \hline \(short\) & \(bhr\) & Value of BHR. \\ \hline \(short\) & \(pi\) & Index of prediction table, calculated by BHR. \\ \hline \(tcfg\_node\_t^{*}\) & \(out\) & Set of edges out. \\ \hline \(tcfg\_node\_t^{*}\) & \(in\) & Set of edges in. \\ \hline \(int\) & \(flags\) & Flags indicating whether the path is feasible. \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Data type of HS node in CFG. The ILP designed in this paper is based on the ILOG/CPLEX format [24]. There are two ILP solvers capable of solving problems in this format: CPLEX, a commercial software, and \(lp\_solver\), a free and open-source alternative. This paper uses \(lp\_solver\) 5.5.0.4 as the third-party ILP solver for calculating the WCET.