WCET Analysis of HLS-Generated Processors Using Abstract Interpretation

Worst-Case Execution Time (WCET) estimation aims at deriving safe upper bounds on program execution time [21]. For the scope of this paper, we focus on static WCET estimation techniques, which compute safe execution-time bounds without executing the program on the target hardware.

Static WCET analysis typically involves two main steps. First, low-level analysis estimates the execution time of small code fragments, known as basic blocks (sequences of instructions with no internal branching except possibly at the last instruction), using an abstract timing model of the processor. Such timing models capture relevant architectural effects, including pipeline behavior, cache effects, and branch prediction, while remaining conservative with respect to actual hardware timing. Second, high-level path analysis identifies the longest feasible execution path in the program’s Control-Flow Graph (CFG), which represents possible control-flow transitions between basic blocks. A commonly used method is the Implicit Path Enumeration Technique (IPET [15]), which formulates WCET computation as an integer linear programming (ILP) optimization problem.

Designing accurate yet safe timing models for static WCET analysis raises several issues:

• $\mathrm{■}$

  Availability of timing information. An abstract timing model must remain consistent with actual hardware behavior, which requires identifying the architectural features relevant to timing analysis and ensuring that sufficient timing information is available. However, detailed timing characteristics of hardware components are not always publicly documented or easily accessible. Therefore, model construction must balance fidelity to hardware behavior with the availability of exploitable timing data.

• $\mathrm{■}$

  State-space explosion. Modern processors exhibit a large number of possible concrete microarchitectural states (pipeline, cache, branch predictor, etc.). Enumerating all concrete states is intractable. This motivates the use of abstraction techniques such as abstract interpretation to compactly represent state sets while preserving safety guarantees [1].

• $\mathrm{■}$

  Composability of timing analyses. Timing effects of different hardware components are often interdependent. Designing composable analyses that allow separate modeling of architectural features while preserving global safety is challenging, particularly in the presence of timing anomalies [16, 4], where locally worst-case microarchitectural events may not correspond to global worst-case execution times. When timing anomalies may occur, exploring hardware states is necessary to obtain sound WCET bounds.

This paper addresses these three challenges by automatically extracting abstract timing models for High-Level Synthesis (HLS)-designed processors. Our focus is on low-level analysis, while standard high-level WCET analysis techniques are assumed to be available at the program level.

High-Level Synthesis (HLS) is a design methodology that analyzes a high-level behavioral description of an algorithm and generates a hardware component that implements this behavior for a given target (e.g., an FPGA or an ASIC with a given technology). The primary objective of HLS tools is to transform an untimed description into a scheduled implementation, assigning each operation to a precise clock cycle. Several scheduling techniques exist, among which loop pipelining is one of the most effective. Loop pipelining overlaps successive iterations of a loop by initiating a new iteration before the previous one has completed. The Initiation Interval (II) of a pipelined schedule (ideally $1$) is the number of cycles to wait before starting a new iteration. As loop pipelining is a static scheduling technique, all possible dependencies must be considered when scheduling operations. Once generated, the resulting cycle duration depends on the target. However, the schedule, which takes the target specifications into account, remains the one determined by the HLS tool.

The synthesis of a pipelined processor using HLS takes as input an Instruction Set Simulator (ISS) and generates the processor hardware. The ISS, illustrated in the left part of Figure 1, is an infinite loop operating on the processor’s registers (including the Program Counter – PC). Using commercial HLS tools to synthesize a pipelined processor yields poor performance because the exact value of the next program counter (PC) must be determined before executing the next instruction. Consequently, II cannot be equal to the ideal value of $1$, because one must wait for the outcome of a conditional branch before knowing the next value of PC.

Recent advances in HLS have introduced Speculative Loop Pipelining (SLP) [7]. This technique speculates on the values produced by an iteration in order to start subsequent iterations as early as possible. SLP is built upon the Gated-SSA [19, 20] representation, a refined variation of Single Static Assignment (SSA) Intermediate Representation (IR) used in compiler frameworks. In SSA, each variable is assigned exactly once, simplifying data-flow analysis; when multiple control-flow paths merge, SSA introduces $\varphi -nodes$ to select the appropriate variable value depending on the execution path taken. In Gated-SSA, $\varphi -nodes$ are represented as multiplexer-like nodes called $\mu -node$ and $\gamma -node$. The former represents loop headers (i.e., the choice between the variable’s value before the loop’s start and the variable’s value from the loop body), whereas the latter represents other reconvergence points in the control-flow. SLP consists of identifying $\gamma -nodes$ with a fast and a slow path, in order to speculate that the fast path is taken. The intermediate representation is then transformed by inserting penalty delays on slow paths (the number of cycles due to pipeline stalls), which increases the reuse distance and improves the achievable minimal II. To preserve the original program semantics, a Finite State Machine (FSM) is inserted to control the speculation logic. The FSM drives the $\gamma -nodes$, verifies the effective value of the control signal, and, depending on the validity of the speculation, triggers some rollback or commit signal.

Figure 1 illustrates a simple speculation scenario in which the next program counter is either PC+4 or the target of a branch instruction starting from an inital pc equal to 0. In this example, we assume that three clock cycles are required to determine if an instruction branches and, if so, at which target address. The Gated-SSA representation of this example is depicted in the central part of Figure 1. To achieve a pipeline with II=1, the SLP technique speculates that the next PC value is PC+4 and generates the right-most representation. We can see the FSM driving the different speculation mechanisms, and the delays inserted on slow paths (delays of $2$ clock cycles compared to a perfect pipeline issuing one instruction per cycle).

Speculative loop pipelining is a key mechanism for generating pipelined processors using HLS. In a conventional pipelined processor, two fundamental speculations are performed: first, that the next instruction address is equal to PC+4 (see Figure 1), and second, that no read-after-write (RAW) dependency exists between consecutive instructions. These assumptions correspond directly to the forms of speculation enabled by speculative loop pipelining.

A notable advantage of using HLS to generate pipelined processors is the ability to explicitly model speculation and precisely identify the sources of pipeline penalty. In the example from Figure 1, the value sent to the FSM directly controls the number of pipeline penalty (delays) and can be used to estimate the WCET of sequences of instructions.

Let us consider a simple core with two instructions add and mul, whose Gated-SSA representation is depicted in Figure 2. This example has two speculation points:

• $\mathrm{■}$

  The first speculation point (${\gamma }_{regs}$-node) speculates on the absence of read-after-write (RAW) dependencies (an instruction reads a value written by a previous instruction) on the registers file. If a dependency (also known as an alias) exists, a penalty delay of one or two cycles (depicted in red) is added, as explained later.

• $\mathrm{■}$

  The second speculation point (${\gamma }_{res}$-node) speculates that the result of the shortest instruction (addition) is used. In case of misspeculation, a two-cycle penalty is incurred, as detailed later.

The program counter $pc$ fetches an instruction from external memory ($[]$ operation after the ${\mu }_{pc}$-node). An instruction is coded as a 5-bit value with: 1 bit for the opcode (0 for an addition, 1 for the multiplication), two bits for the source register rs, and two bits for the destination register rd. The extract block splits the instruction into its three parts.

The control part below the extract block checks for a dependency (alias) between a register write rd from the two previous cycles, and a register read rs in the current iteration. The two $\delta$-nodes keep the values of rd of the two previous cycles. Their purpose is not to stall the pipeline but to carry over values from the previous cycle to the current one. At the beginning of an iteration, ${\delta }_1$ saves the value of rd of the current iteration, and forwards the value saved in the previous cycle, where ${\delta }_2$ saves the value forwarded by ${\delta }_1$ and forwards its current value. The values of ${\delta }_1$ and ${\delta }_2$ are compared with the current rs.

The result of the comparison controls a set of multiplexers that controls the first speculation point (${\gamma }_{regs}$) in our running example. If the alias distance is 0, (i.e., current iteration aliases with the last cycle), the core goes through 2 penalty cycles (represented by the two red rectangles in Figure 2) to wait for the write operation to complete; if the alias distance is 1, then the core only goes through one penalty cycle; otherwise, there are no penalties. Once the value is ready to be read, the $[]$-node reads the value of register rs.

In our running example, addition and multiplication cannot be performed simultaneously. Since the multiplication takes three cycles, a structural hazard occurs when a multiplication starts and must be handled. Thus, the second speculation point, at ${\gamma }_{res}$, controlled by the opcode value, causes two penalties when a multiplication occurs. Once the operation is completed, the result is written in the register file at the address rd (with the $\alpha$-node).

Both the output of the alias detection and the opcode are fed to the FSM, which adds the appropriate number of penalties based on the signals’ values during execution. $P_{res}$ represents the number of pipelined penalties caused by ${\gamma }_{res}$, and $P_{regs}$ those caused by ${\gamma }_{regs}$.

Unlike most analyses in the state of the art, we do not directly model the core pipeline; instead, we determine the number of penalties it incurs.

The key point of speculative loop pipelining is the ability to produce a pipeline with an II equal to 1 (i.e., a new iteration/instruction starts at every cycle). In such a design, where an instruction starts speculatively every cycle, in case of a misspeculation for an instruction $I$, the subsequent instructions that have started after $I$ are canceled. Then, the execution of $I$ is stalled for a given number of cycles to wait for the correct value before starting the next iteration in a correct state.

In a processor core generated by such flows, speculation depends on both the core’s internal state and its inputs (e.g., the instruction fetched). Thus, we need to model all parts of the processor core that are involved in speculation. To do so, for a given core, we construct a timing model represented by the 4-tuple $(Q,I,F,T)$. Each component of the tuple will be defined more precisely in the following sections.

• $\mathrm{■}$

  $Q$ is the state-space of possible core states. $Q$ is a set of n-tuples, each n-tuple storing the values of the variables; $Q$ is an abstract state of the processor, that selects variables relevant to timing analysis only, and allows for unknown variables;

• $\mathrm{■}$

  $I$ is the set of possible inputs, each being defined by an m-tuple containing the values of input variables;

• $\mathrm{■}$

  $F$ is a penalty estimator function $F:Q\times I⟶P(\mathbb{N})$, with $P(\mathbb{N})$ the power set of $\mathbb{N}$ that gives for a given state $q\in Q$ the set of possible penalties throws by this state;

• $\mathrm{■}$

  And $T$ is the transition function from a state $q$ with an input $i$ and $p$ penalties.

From a timing estimation perspective, the central part of the model is the $F$ function. While $T$ lets us traverse the states the processor passes through during the execution of a basic block, $F$ captures the possible timing penalties incurred during execution.

We observe in Figure 4 that after the first iteration, our analysis has three possible states from which the next iteration can start. Our analysis repeats the previous steps for each possible state to obtain the next initial states of the third instruction, and again to obtain the final states (in green in Figure 4), which are connected to the $sink$ node. The rapidly increasing number of states to explore raises the issue of the applicability of our analysis to a real sequence of instructions on a real processor.

Fortunately, because of the abstraction in our model, many possible initial states are equivalent within an iteration. For instance, in Figure 4, all initial states of the third iteration are equivalent. Our merging process merges nodes that are identical and further have an incoming edge with the same label (i.e., the number of penalties). In our example, the blue nodes of Figure 4 are merged into a single node. This merge strategy drastically reduces the number of states to explore.

If we look at the sequence of states depicted by the blue edges in Figure 4, we notice that this sequence cannot occur in any execution. Indeed, the four penalties introduced by the second iteration are decomposed as follows: two cycles for the multiplication penalty, two cycles for an alias between rs and rd from the previous instruction, and one in ${\delta }_1$. And if we look at the content of ${\delta }_1$ and the value of rs, we can see that the two are not equal and thus cannot alias.

The presence of this sequence of states stems from how both $T$ and $F$ work. To compute the next value of a state variable or the value of a control signal, our analysis extracts the logic from all input and state variables and routes it to the state-variable operator ($\mu$-nodes or $\delta$-nodes) or the FSM operator. Then, it assigns each input and state variable its current value and performs constant propagation through the extracted logic. In our example, the select signal of the right-most multiplexer in Figure 3 is the result of the comparison between rs and rd stores in ${\delta }_1$. Since, at this state, these two values are constant ($11$ for rs and $01$ for rd) and different, the select signal is false, and the multiplexer forwards the value of the left-most multiplexer. The select signal of the latter depends on an unknown value, the content of ${\delta }_2$, and thus is itself unknown. Since the multiplexer can forward either $0$ or $1$, the signal sent to the rightmost multiplexer is unknown, and thus the control signal sent to the FSM is unknown.

Although we did not observe this phenomenon in the processor we synthesized (see Section 5), it could happen on other architectures that the longest path includes these impossible sequences of states, resulting in pessimistic WCET estimates. A different arrangement of the multiplexer-tree can prune these impossible state sequences, while creating others at other points of the analysis.

To our knowledge, only SpecHLS HLS flow [10] implements the speculative loop pipelining technique on which our technique is based. Thus, we decide to use SpecHLS, which heavily relies on the MLIR compilation framework¹¹1https://mlir.llvm.org/ for analyses and code generation.

The Heptane WCET estimation tool [13] was used for WCET estimation at the task-level. We additionally implemented a handcrafted timing model as a baseline.

We performed the analysis on a micro-architecture model corresponding to the 5-stage rv32i RISC-V processor without forwarding. This model has two speculations. The first one speculated that the register currently read has no write operation in the two previous cycles, and the second one that the instruction is not a branch, which corresponds to the model used by Feuilletin et al. [8] to evaluate their analysis.

We use a subset of the Mälardalen benchmarks [11] for our experiments. This subset excludes benchmarks with floating-point operations, as our architecture does not support them and they must be emulated in software. Since loop bounds for emulated floating-point operations, required by Heptane, are difficult to derive due to the complexity of their implementation, we chose, for simplicity, to remove benchmarks that use floating-point operations.

We have compared our analysis to the PGA analysis previously published in [8]. PGA estimates the WCET of a basic block by unrolling the temporal model to create a graph and replacing fetch logics with the sequence of instructions. Then it performs constant propagation and dead-code elimination passes to specialize each part of the graph, and then uses a longest-path algorithm to determine the path in the graph that incurs the most penalty. Their timing model differs from ours: they do not perform any exploration of possible processor states, and further manage aliases between instructions in a safe yet pessimistic way. We implemented both analyses from a single run of the SpecHLS flow.

The baseline timing model implemented in Heptane was slightly modified to match the processor core we generated. This handcrafted model uses a reservation table to implement alias-detection logic and associated stall penalties, along with the branch instruction penalty. Since the microarchitecture does not implement advanced features such as cache or dynamic branch speculation, the handcrafted model is simple and small yet accurate.

The first experiment compares the proposed approach with a handcrafted pipeline model and the PGA analysis previously published in [8]. The results are summarized in Table 1. The table displays the raw WCET estimates for the three techniques, as well as the ratio of the proposed approach to the existing approaches.

It is important to note that the experimental results for PGA are slightly different than those reported in [8]. Indeed, in their original work, Feuilletin et al. considered that the first instructions of a basic block could not alias with previous ones, which can be unsafe. In the numbers reported in Table 1, we consider for all three techniques that the first instruction may alias with previous ones, resulting in a pessimistic but safe WCET.

We observe that the proposed approach is less pessimistic than PGA, reducing the WCET estimate by an average of 3.6%. This difference is due to the fact that PGA, instead of exploring states, always considers the worst-case penalty at the instruction level, resulting in more pessimistic WCET estimates. The proposed approach is also as precise as the handcrafted model, always returning the same WCET estimate. This shows that our analysis, for this simple core, achieves to model the temporal behavior of the microarchitecture.

The second experiment evaluates the scalability of the proposed approach.

We first analyze the efficiency of the merging strategy proposed in Subsection 4.1. Figure 5 depicts the average number of states explored per instruction with and without the merging strategy, represented for different basic block sizes. For convenience, we only selected blocks with fewer than 30 instructions, which represent 95% of all basic blocks analysed. We observe that, with the merging strategy, the shorter the basic block, the higher the number of states per instruction. This tendency is due to the state of basic block analysis with value unknown, which leads to the creation of several states at the start of the basic block analysis. These states are quickly merged together when analyzing the next instructions. On average, across all basic blocks analyzed, the analysis used 1.6 states per instruction, since small basic blocks are the most common.

Without the merging strategy, the number of states per instruction does not decrease with the size of the basic blocks. As with the merging strategy, the unknown initial states yield a certain number of states, with more and more variables known. Thus, each resulting state does not split into many other states, leading to a constant number of states throughout the analysis. On average, across all basic blocks analyzed, the analysis used $2.62$ states per instruction.

The analysis time using Heptane has also been measured. Across all benchmarks, the average analysis time using the proposed technique is 13 seconds (ranging from 0.47 seconds for fibcall to 87 seconds for nsichneu). If we do not use the merging strategy, the average analysis time is 28 seconds, ranging from 0.51 (fibcall) to 203 seconds (nsichneu). This is 20% longer than the PGA analysis we have reimplemented, and 94$\times$ longer than the handcrafted model.

Our analysis is implemented within the MLIR framework, which introduces significant overhead, whereas the handcrafted model consists of small, self-contained C code. A previous analysis, PGA, is also implemented in MLIR and therefore suffers from the same overhead. However, PGA does not explore different execution paths and performs constant propagation and dead-code elimination only once per basic block. In contrast, our analysis applies these passes at each instruction to enable path exploration, which results in higher execution time compared to PGA. The execution time of our approach is largely tied to the current implementation, and there remains room for improvement, for example by generating C code rather than relying on the MLIR framework.

Our analysis was applied to a simple five-stage RISC-V core. In this analysis, the different memory components (data memory and register file) are not abstracted away, and all accessed values are treated as unknown. For more complex microarchitectural features, such as caches or branch prediction, an appropriate level of abstraction is required to model array-based structures.

Lastly, the runtime of our analysis is tied to the complexity of the architecture and is likely to increase for more complex architectures featuring caches, superscalar execution, and out-of-order execution. The ability of HLS tools to generate such complex architectures has not yet been demonstrated and remains the subject of future work.

A timing model is required to estimate the WCET of basic blocks in timing analysis tools [21]. This model does not need to concretely implement all the functionality of the target hardware. Instead, a simplified model that is conservative regarding the hardware’s timing behavior is sufficient.

The complexity of deriving a timing model strongly depends on the class of processor under consideration. For simpler processors featuring in-order pipelines and no caches, constructing the timing model is relatively straightforward, although still time-consuming. It essentially simulates the flow of instructions through the processor pipeline while accounting for variations in functional unit latencies and memory access times.

For more complex architectures that incorporate performance-enhancing features such as caches, the different hardware components can be analyzed separately (e.g., performing a dedicated cache analysis). Abstract interpretation is commonly used to avoid enumerating all possible architectural states (for instance, abstract cache states are employed instead of concrete cache states [1]). The derived worst-case behavior of each architectural feature can then be incorporated into the pipeline analysis. However, this compositional approach is valid only for architectures that do not exhibit timing anomalies [4]. A typical timing anomaly occurs when a locally favorable event (e.g., a cache hit) results in a longer overall execution time than a less favorable event (e.g., a cache miss).

In architectures exhibiting timing anomalies, constructing a timing model becomes significantly more complex. The analyses are less modular and require a more integrated treatment of architectural features. In particular, they involve some form of exploration of possible processor states (e.g., cache hit or miss information within the pipeline model). For example, Wilhelm [22] enumerates abstract pipeline states to account for timing anomalies and uses Binary Decision Diagrams (BDDs) to mitigate state-space explosion. WCET estimation techniques based on model checking have also been proposed [6, 5, 17], demonstrating that complex architectures (including caches and, in [17], branch prediction) can be modeled to derive precise WCET estimates. However, all authors report state-space explosion for certain benchmarks, even in the absence of timing anomalies. Our technique is similar to [22] in its use of abstract interpretation to enumerate abstract architectural states. Likewise, as in model-checking-based approaches, we explore all possible (abstract) architectural states. Our main distinguishing feature compared to these two classes of techniques is the automatic extraction of the timing model.

The first attempt at automatically extracting timing models from a VHDL representation was presented by Schlickling et al. in [18]. Their technique first prunes the VHDL code to reduce its size. It then automatically extracts the state variables, along with part of the logic used to compute the next state of each pipeline stage. In contrast to our approach, theirs requires user interaction to complete the model extraction process and, moreover, produces very large models.

A technique for the reverse engineering of Chisel hardware designs is presented in [3]. This approach reconstructs the pipeline datapath from the Chisel source code. The resulting datapath must be manually validated. Moreover, the technique excludes control-path extraction, making it unsuitable for direct WCET estimation.

Amalou et al. propose an automatic derivation of timing models for WCET analysis based on machine learning techniques [2]. While the model derivation process is fully automated, the models are trained on empirical data and therefore do not provide formal safety guarantees. As a result, such models may not be suitable for highly time-critical software.

Feuilletin et al. [8] propose a technique that automatically extracts processor timing models from an HLS flow. Their analysis makes conservative assumptions regarding instruction dependencies. Moreover, it systematically relies on local worst-case assumptions to estimate the WCET of a basic block. As a result, the approach is not applicable to processors exhibiting timing anomalies. In contrast, our technique can handle timing anomalies, albeit at the cost of increased analysis time.