Sidharta Andalam

Roopak Sinha

Partha S Roop

Alain Girault

Jan Reineke

Precise Modelling of Instruction Cache Behaviour

Keywords: Instruction Cache Analysis, WCET, worst case execution analysis, direct mapped cache Analyse du cache instructions, WCET, analyse du temps d'exécution au pire cas, cache

Safety critical real-time applications in aviation, automotive and industrial automation have to guarantee not only the functionality, but also the timeliness of the results. Here, a deadline is associated with the software tasks, and a failure to complete prior to this deadline could lead to a catastrophic consequences. Hence, for the correctness of real-time systems, it is essential to be able to compute the worst case execution time (WCET) of the tasks in order to guarantee their deadlines. However, the problem of WCET analysing is difficult, because of processors use cache-based memory systems that vary memory access time significantly. Any pessimistic estimation of the number of cache hits/misses will result in loose precision of the WCET analyses, which could lead to over use of hardware resources. In this paper, we present a new approach for statically analysing the behaviour of instructions on a direct mapped cache. The proposed approach combines binary representation and a new abstraction that reduces the analysis time without sacrificing the precision. This is unlike the existing cache analysing approaches where either precision or scalability (analysis time) is sacrificed. Experimental results are presented that demonstrate the practical applicability of this analysis.

Introduction

Most applications can benefit significantly from a fast, cheap and large memory. However in reality, as the memory gets faster, the cost increases and the size decreases. For example, caches are fast and small, but expensive compared to hard disks which are slow, cheap and large. This restriction has forced the computer architects to physically place the fast and smaller memories close to the processor. In contrast, slower and larger memories are placed further away from the processor. Hence, we have a hierarchy of memories as presented in Figure 1. Memory hierarchies are effective because, during an execution of a program, the frequency of accessing storage units at any particular level is more than the frequency of accessing storage at the next lower level. Hence, the next level storage units can be slower. The overall effect is a large memory unit that is very cost effective. In embedded systems, as the application complexity is growing continuously, the complexity of the underlying memory hierarchy is also increasing. For example, for a simple automatic door control, the computation is very simple and hence a memory architecture with only registers and main memory could meet the requirements. In contrast, applications in automotive industry (such as engine control unit) are much more complicated and would require a complex memory hierarchy [START_REF] Wilhelm | Symbolic state traversal for WCET analysis[END_REF].

After registers, caches are the next nearest memory to the processor. They are used for temporary storage of instructions, such that future requests can be processed much faster. They act as a bridge between the fast processors and the slower main memory. Caches are effective, because of the following two principles:

1. Temporal locality: Memory locations that are accessed recently are likely to be accessed again, e.g., cycle through instructions of a loop.

2. Spatial locality: Memory locations that are close to the locations that are currently accessed are likely to be accessed soon, e.g., reference to instructions in sequence.

Inria

When a processor requests the cache for data at a location in the main memory, the cache first checks it's memory contents. If the requested data is in the cache (cache hit), the data is sent to the processor. Otherwise, if the data is not in the cache (cache miss), it is copied from the main memory into the cache and then forwarded to the processor. However, during this copy, if the cache is already full, a replacement policy will decide which location of the cache memory is to be replaced by the new data. The performance of a cache is measured by the number of cache misses (or cache hits). Thus, the goal of the replacement policy is to reduce the number of cache misses. There are several policies and some are architecture specific. The cache architectures are either classified as set-associative or direct mapped caches [START_REF] Hennessy | Computer Architecture -A Quantitative Approach[END_REF]. For a set associative cache, each location of the main memory is mapped to more than one location in the cache memory. In general the following three policies are used during replacement [21]:

• Least recently used (LRU): replaces the least recently accessed memory location.

• First in first out (FIFO): replaces the memory that has been in the cache for the longest amount of time.

• Pseudo-LRU (PLRU): is a binary tree based approximation of the LRU policy. The history of the access define the structure of the tree and the leaves represent the cache lines. For more details refer to [START_REF] Reineke | Caches in WCET Analysis[END_REF].

In contrast, for a direct mapped caches, the replacement policy is very simple. Each location of the main memory is mapped to exactly only one location in the cache memory. This policy does not require any history bits and updating, unlike the replacement policies mentioned above. Most embedded applications use Direct Mapped Caches because of their simple design, low complexity (requires small hardware), and low power consumption. It also simplifies the static analysis that is required for hard real time systems.

Alternatively, to achieve timing predictability and to simplify static timing analysis, there has been a shift towards predictable memory hierarchy for hard real-time systems. One such approach is to use a cache locking mechanism [START_REF] Puaut | Scratchpad memories vs locked caches in hard real-time systems: a quantitative comparison[END_REF]. In this approach, the contents of the cache are decided at compile time and are loaded prior to the execution of the program. This simplifies the analysis and provides a predictable platform. However, this significantly reduces the throughput. This simple approach has been further extended to dynamically reload and lock the cache at statically determined control points [START_REF] Puaut | WCET-Centric Software-controlled Instruction Caches for Hard Real-Time Systems[END_REF]. This increases the throughput at the expense of the analysis time.

Recently, scratchpad memories (SPMs) have been introduced as an alternative to caches for predictable systems. In SPMs, the allocation and replacement decisions are made by software, guided by the decisions made at compile time. In contrast, the allocation and replacement of traditional caches are done dynamically, guided by the history of the cache states. Recent work on SPMs focuses on developing software allocation algorithms [START_REF] Schoeberl | A time predictable instruction cache for a Java processor[END_REF], [START_REF] Suhendra | Scratchpad Allocation for Concurrent Embedded Software[END_REF], [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] and/or designing tailored architectures with SPMs [START_REF] Schoeberl | A time predictable instruction cache for a Java processor[END_REF], [START_REF] Lickly | Predictable Programming on a Precision Timed Architecture[END_REF], [START_REF] Liu | Precision Timed Machines[END_REF].

In this paper, we focus only on single core processors with direct mapped caches. We present two prominent related works in analysing direct mapped caches. In the NUS approach [START_REF] Negi | Accurate Estimation of Cache-Related Preemption Delay[END_REF], the problem of computing all possible cache states is mapped to a problem of computing the least fixed point. This approach performs very precise analysis. However, as the program size increases, this approach experiences state-space explosion and the analysis time grows exponentially. To address this issue, the same research group has formulated a new probabilistic approach for modelling cache behaviour [START_REF] Liang | Static analysis for fast and accurate design space exploration of caches[END_REF]. It is used for design space explorations and reduces overall analysis time by exploiting the structural similarities among related cache configurations. Experimental results indicate that their new probabilistic based analysis is 24 to 3855 times faster than simulation. Also, they have employed the idea of cache conflict graphs (CCF) in [START_REF] Li | Accurate timing analysis by modeling caches, speculation and their interaction[END_REF]. This work analyses one cache line at a time and presents a more scalable approach. However, it abstracts the relation between cache lines, thus, sacrificing precision. Also, it would be interesting to quantitatively compare the precision and the analysis time with other existing techniques, like the Absint approach [START_REF] Ferdinand | Cache Behavior Prediction by Abstract Interpretation[END_REF], [START_REF] Reineke | Caches in WCET Analysis[END_REF]. The Absint approach performs an abstraction based WCET analysis by sacrificing precision for scalability. As a result, it is the preferred approach for analysing cache based architectures for industrial applications [START_REF] Souyris | Computing the worst case execution time of an avionics program by abstract interpretation[END_REF], [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF], [START_REF] Sehlberg | Static WCET Analysis of Real-Time Task-Oriented Code in Vehicle Control Systems[END_REF].

The organisation of this paper is as follows. In Section 2, we formalise the cache analysis problem. In Sections 3 and 4 we present two prominent related works in analysing direct mapped caches. First, the NUS approach [START_REF] Negi | Accurate Estimation of Cache-Related Preemption Delay[END_REF] is presented in Section 3. Second, the Absint approach [START_REF] Ferdinand | Cache Behavior Prediction by Abstract Interpretation[END_REF] is presented in Section 4. We compare both approaches in Section 5. In Section 6, we present the proposed cache analysis approach (UoA approach), along with some optimisations. In Section 7 we present a comparisons between all three (NUS, Absint and UoA) approaches. Finally, in Section 8 we conclude the chapter with some discussions.

Cache Analysis

Cache model

The first step in the cache analysis is the creation of a suitable cache model. Before we formally define the cache model, we provide an illustrative description. Cache analysis requires the following information:

1. A control flow graph (CFG). This is extracted from the binaries of an embedded program [START_REF] Theiling | Extracting safe and precise control flow from binaries[END_REF]. The CFG contains basic blocks which are annotated with instructions that are executed in this block. An example CFG is presented in Figure 2(a). It contains nine basic blocks, B1 to B9. The basic block B1 is annotated with four instructions m1, m2, m3 and m4 that are executed in this basic block. The entire program (CFG) has eight different instructions m1 to m8.

2.

A mapping of all instructions to cache lines. Since, the number of instructions in a program is usually greater than the number of cache lines, more than one instruction is mapped to the same cache line. For the example CFG (presented in Figure 2(a)), we present the instructions to cache lines mapping using Figure 2(b). The cache has four cache lines c 0 , c 1 , c 2 , c 3 . Instructions m1 and m5 are both mapped to the cache line c 0 . This means that during program execution, cache line c 0 can contains either m1 or m5 or nothing (when empty).

The above information can be used to map the instructions in each basic block to the cache lines. E.g., for block B1, instructions m1, m2, m3, m4 are mapped to cache lines c 0 , c 1 , c 2 , c 3 respectively (as presented in Figure 2(b)). If we enforce C = {c 0 , c 1 , c 2 , c 3 }, the set of cache lines, to be an ordered set, then the instructions of B1 can be described using a vector [m1, m2, m3, m4] where the index of the i th element corresponds to the i th cache line. E.g., the 2 nd element m2 corresponds to the 2 nd cache line c 1 . Similarly, the basic block B2 has only one instruction m5 that is mapped to cache line c 0 and the rest of the cache lines have no instructions (represented using the symbol ∓). Hence, the instructions of B2 can be described using the vector [m5, ∓, ∓, ∓].

For the rest of this section, we formalise the cache model, the behaviour of the cache, and the cache analysis problem.

Definition 1 (Cache model). The cache model for a given program is defined as a tuple CM = I, C, CI, G, BI , where: • I is a finite set of instructions and |I| is the total number of instructions in the program.

• C = {c 0 , c 1 , . . . , c N -1 } is an ordered set of cache lines. N = |C| is the total number of cache lines.

• CI : C → 2 I is the cache line to instructions mapping function. For a cache line c ∈ C, CI(c) is a subset of I representing the set of instructions that are mapped to cache line c.

We restrict CI such that for any two cache lines c k and c l , CI(c k ) ∩ CI(c l ) = ∅ and further

N -1 k=0
CI(c k ) = I i.e., CI partitions I into N partitions, where each partition represents the instructions mapped to a given cache line.

Also, we define the instruction to cache line mapping function IC :

I → C. For an instruction i ∈ C, IC(i) = c, where i ∈ CI(c). • G is a directed graph G = B, b init , E where:
-B is a finite set of basic blocks.

b init ∈ B is the initial basic block.

-E ⊆ B × B is the set of edges. For short hand, (b 0 , b 1 ) ∈ E is represented using b 0 → b 1 .
• BI : B → (I ∪ {∓}) N is the block to instruction mapping function. For any given basic block

b ∈ B, BI(b) = [inst 0 , inst 1 , . . . , inst N -1 ]. For any i ∈ [0, N -1], BI(b)[i] is the instruction mapped to the i th cache line c i ∈ C. Thus, BI(b)[i] ∈ CI(c i ) ∪ {∓}.

Illustration of the cache model

Using Figure 2, we illustrate the cache model CM = I, C, CI, G, BI as follows:

• I = {m1, m2, m3, m4, m5, m6, m7, m8} and |I| = 8. , m6, m3, m4] and BI (B8)[0] = ∓, which represents that block B9 does not contain any instruction that is mapped to the cache line c 0 . The order of the instructions in the vector are based on the mapping of the instructions to the cache lines. It is not based on the order of the instructions specified by the programmer, i.e., BI(B8) = [∓, m3, m4, m6].

• C = {c 0 , c 1 , c 2 , c 3 } is an ordered set and N = |C| = 4. • CI(c 0 ) = {m1, m5} and IC(m1) = c 0 . • G = (B, b 0 , E) where B = {B1, B2, . . . , B9}, b 0 = B1 and E = {(B1, B2), (B2, B3), . . .}. • BI(B1) = [m1, m2, m3, m4] and BI(B1)[1] = m2. Similarly, BI(B8) = [∓

Cache states

We describe the behaviour of the cache by first describing cache states. A cache state describes the instructions in the cache at some instance in time. It is described as a vector [inst 0 , inst 1 , . . . , inst N -1 ] where each inst i represents the instructions contained in cache line c i ∈ C.

For the example CFG shown in Figure 2(a), when the program starts executing, we assume the cache is empty. This is represented as the cache state cs = [ , , , ]. Instructions are loaded into the cache as the basic blocks are executed (starting from the initial block). E.g., after executing the basic block B1 the cache state is cs = [m1, m2, m3, m4].

Generally, the status of the cache may be unknown when a block is being analysed. We used the symbol ⊥ to represent an unknown instruction in a cache line. E.g., cs = [⊥, ⊥, ⊥, ⊥] represents the status of every cache line is unknown. This notion of unknown cache state is used during the cache analysis and is explained later in Section 3.

Note that a cache state has identical structure to the block to instructions mapping function BI(b) for any block b ∈ B. E.g., The cache state after executing B1 is cs = [m1, m2, m3, m4] and also, BI(B1) = [m1, m2, m3, m4]. The cache state represents the instructions in the cache, while the function BI represents the instructions that are executed by the basic block. This identical structure simplifies the cache analysis as simple comparison between vectors allows us to analyse the cache misses. This is later explained in later part of this section.

We now define the cache states.

Definition 2 (Cache state). A Cache state cs ∈ (I ∪ { , ⊥}) N , can be described as a vector [inst 0 , inst 1 , . . . , inst N -1 ] where each element cs[i] represents an instruction in cache line c i . Further, we restrict cache states such that, for any

i ∈ [0, N -1], cs[i] ∈ CI(c i ) ∪ { , ⊥}.
We denote cs = [ , . . . , ] as a empty cache state where all the elements of the vector are . Similarly, we denote cs ⊥ = [⊥, . . . , ⊥] as a unknown cache state where all the elements of the vector are ⊥. Also, the set of all cache states is defined as CS.

Before we illustrate cache states, we introduce two key terms essential to cache analysis. For any basic block b, the Reaching cache states (RCS) represent the set of cache states prior to the B2: m5

B6: m2 m3 m4
B7: m6 m7 m8
B8: m3 m4 m6 c0 m5 c1 m6 c2 m7 c3 m8 c0 m5 m5 c1 m6 m2 c2 m7 m3 c3 m8 m4 c0 c1 c2 c3 c0 m1 c1 m2 c2 m3 c3 m4 c0 m5 c1 m2 c2 m3 c3 m4 c0 m5 c1 m2 c2 m3 c3 m4 c0 m5 c1 m6 c2 m3 c3 m4
Figure 3: Illustration of the cache states.

Using Figure 3, we illustrate reaching/leaving cache states of a block. Initially the cache is empty. The state of the cache is cs = [ , , , ]. After the execution of block B1, cache lines c 0 , c 1 , c 2 , c 3 will contain instructions m1, m2, m3, m4 respectively, resulting in the state [m1, m2, m3, m4]. The cache state [ , , , ] is the state of the cache prior to the execution of the basic block B1. Thus, RCS B1 = {[ , , , ]} is the set of reaching cache states of block B1. Similarly, LCS B1 = {[m1, m2, m3, m4]} is the set of leaving cache states of block B1.

The leaving cache state of B1 is also the reaching cache state of B2, RCS B2 = LCS B1 . Block B2 has only one instruction m5, and is mapped to cache line c 0 . Thus, the previous instruction in line c 0 will be replaced by m5. Since the RCS B2 = {[m1, m2, m3, m4]}, after executing the instructions in B2, the resulting leaving cache state is

LCS B2 = {[m5, m2, m3, m4]}.
Now, the control reaches a branch due to which, it is possible to execute either block B6 or block B7. In this case, RCS B6 = LCS B2 = RCS B7 . After executing blocks B6 or B7, the state of the cache is either [m5, m2, m3, m4] or [m5, m6, m7, m8].

Block B8 has two incoming edges: from blocks B6 and B7. In this case, in order to compute RCS B8 , we need to join LCS B6 and LCS B7 . There are various approaches to describe this join function [START_REF] Negi | Accurate Estimation of Cache-Related Preemption Delay[END_REF], [START_REF] Ferdinand | Cache Behavior Prediction by Abstract Interpretation[END_REF]. This join function is the key difference between existing approaches and could dictate the precision and the scalability of the cache analysis. Later in this chapter, we formally present several join functions. See the summary in Section 7

For now, we assume the join function is a union over the set of cache states. Thus, RCS B8 = LCS B7 ∪ LCS B6 , resulting in RCS B8 = {[m5, m2, m3, m4], [m5, m6, m7, m8]}. After execution of block B8, for both reaching cache states the resulting leaving cache state is [m5, m6, m3, m4]. Thus, the LCS B8 = {[m5, m6, m3, m4]}.

Analysing the cache states

The purpose of cache analysis is to compute the number of cache misses experienced during the execution of every basic block. For example, for block B8 consider the cache state cs = [m5, m2, m3, m4] before executing the block. Since cs [START_REF]MicroBlaze Processor Reference Guide[END_REF] = m2, the cache contains the instruction m2 on the cache line c 1 , before executing B8. Now, BI(B8) = [∓, m6, m3, m4] and BI(B8) [START_REF]MicroBlaze Processor Reference Guide[END_REF] = m6 for cache line c 1 . This means, for cache line c 1 , the cache contains the instruction m2, whereas the block needs to execute m6. Since, we have a mismatch (BI(B8) [START_REF]MicroBlaze Processor Reference Guide[END_REF] = cs [START_REF]MicroBlaze Processor Reference Guide[END_REF]), B8 has a cache miss during the execution of instruction m6 on the cache line c 1 .

Similarly, since BI(B8) [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] = m3 = cs [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF], we have a cache hit. Also, BI (B8)[0] = ∓, which represents that block B8 does not execute an instruction from cache line c 0 . Therefore, B8 can not have a miss for cache line c 0 , regardless of the content of a reaching cache state. Thus, a cache miss on a cache line c i can only occur when the block b has an instruction that can be mapped to a cache line c i ( i.

c i ∈ C with i ∈ [0, N -1] is defined as follows: mc(b, cs, c i ) = 1 : if BI(b)[i] = ∓ ∧ BI(b)[i] = cs[i] 0 : otherwise
We extend the function mc to return the total number of misses for a block b and a cache state cs as, mc : B × CS → N 0 where, , m6, m3, m4], we now illustrate the mc function using Figure 4. For all cache lines c i ∈ C, the figure shows that there is only one cache miss and it occurs on cache line c 1 , because instruction m2 is present in the reaching cache state cs while the block needs instruction m8. Thus, mc(B8, cs, c 1 ) = 1. Similarly, mc(B8, cs, c 0 ) = 0, mc(B8, cs, c 2 ) = 0 and mc(B8, cs, c 3 ) = 0. Hence, mc(B8, cs) = 0 + 1 + 0 + 0 = 1. Thus, only one cache miss occurs during the execution of block B8 for reaching cache state of [m5, m2, m3, m4].

mc(b, cs) = N -1 i=0 mc(b, cs, c i ) 2.3.1 Illustration c i c 0 c 1 c 2 c 3 cs = [m5 m2 m3 m4] BI(B8) = [ ∓ m6 m3 m4] mc(B8, cs, c i ) = 0 1 0 0 = = = mc(B8, cs) = 0 + 1 + 0 + 0 = 1
The mc function computes the number of cache misses for a given reaching cache state and a basic block. However, if a block has more than one reaching cache states, the number of cache misses can vary. For cache analysis, we are interested in finding the best case and the worst case number of cache misses that may be experienced by a basic block. Illustration of wmc and bmc Using the reaching caches states for B8 (RCS B8 ), we now illustrate the functions wmc and bmc. Since, RCS B8 contains two cache states of {[m5, m2, m3, m4], [m5, m6, m7, m8]}, using the mc (B8, [m5, m2, m3, m4]) = 1 or mc (B8, [m5, m6, m7, m8]) = 2. Since, the maximum number of misses is 2, thus, wmc(B8, RCS B8 ) = 2. Similarly, the function bmc(B8, RCS B8 ) = 1.

Cache analysis problem

The cache analysis problem consists of two sub problems. The first sub problem is to compute all the possible reaching cache states for every basic block in the given cache model. The second sub problem is to compute the number of cache misses in the best case and the worst case, using the reaching cache states computed in sub problem one. Definition 6 (Cache Analysis Problem). Given CM , the cache analysis problem can be stated as the computation of:

1. All possible RCS b for every block b ∈ B. We refer to this first problem as sub problem one. Different cache analysis approaches differ in how they compute sub problem one (presented in Definition 6). We present two existing approaches, the NUS approach [START_REF] Negi | Accurate Estimation of Cache-Related Preemption Delay[END_REF] and the Absint approach [START_REF] Ferdinand | Cache Behavior Prediction by Abstract Interpretation[END_REF] to solve the cache analysis problem. In Table 1 we present a summary of the symbols and the definitions that are presented so far. The NUS approach

Symbol

We first present two functions, join and transfer, that compute the of reaching/leaving cache states of basic blocks. These two functions are used in the cache analysis algorithm, employed by this approach, to compute all possible reaching cache states of every basic block of a cache model (sub problem 1, Definition 6).

The NUS join function

The NUS join function describes how to compute the reaching cache states of a basic block when the block has more than one incoming edges. E.g., in Figure 3, the basic block B8 has two incoming edges: from blocks B6 and B7. To compute RCS B8 we need to join LCS B6 and LCS B7 . A simple join function could be described as an union over the sets of reaching cache states, i.e., RCS B8 = LCS B6 ∪ LCS B6 . However, in the NUS approach, during the computation of the reaching cache states unknown cache states (cs ⊥ ) are introduced as part of the analysis (later explained in Algorithm 1). This introduces spurious cache states that must be removed as described in the NUS approach [START_REF] Negi | Accurate Estimation of Cache-Related Preemption Delay[END_REF]. Given two cache states cs 1 and cs 2 , cs 1 is subsumed by cs 2 , if for all cache lines c i , the instruction in cs 2 is equal to the instruction in cs 1 (cs

2 [i] = cs 1 [i]) or the instruction in cs 1 at cache line c i is unknown ⊥ (∀i, cs 2 [i] = cs 1 [i] or cs 1 [i] = ⊥).
In this case, we can remove cs 1 , as it does not contain any extra information compared to cs 2 . For example, let RCS b = LCS 1 ∪ LCS 2 , it contains two cache states cs 1 = [m1, ⊥, ⊥, ⊥] and cs 2 = [m1, ⊥, m2, ⊥]}. Since cs 1 is subsumed by cs 2 , we can reduce the reaching cache states of b to RCS b = {[m1, ⊥, m2, ⊥]}. Also, a cache state cs ⊥ = [⊥, ⊥, . . . , ⊥] will always we subsumed by any other cache state. This idea of subsumed cache states is further explained during the fixed point computation (see Section 3.3).

This join function for the NUS approach is defined in Definition 7.

Definition 7 (NUS join function). The NUS join function is J N U S : 2 CS × 2 CS → 2 CS where, for any two sets of cache states CS 1 ⊆ 2 CS and CS 2 ⊆ 2 CS ,

J N U S (CS 1 , CS 2 ) =CS 1 ∪ CS 2 \ {cs 1 ∈ (CS 1 ∪ CS 2 )|∃cs 2 ∈ (CS 1 ∪ CS 2 ) ∧ S N U S (cs 1 , cs 2 )}
where, S N U S : CS × CS → {true, f alse} where, for any cs 1 , cs 2 ∈ CS,

S N U S (cs 1 , cs 2 ) = true : if ∀i ∈ [0, N -1], cs 2 [i] = cs 1 [i] or cs 1 [i] = ⊥ f alse : otherwise cs 1 cs 2 S N U S (cs 1 , cs 2 ) [⊥, m2, ⊥, m4] [m5, m2, ⊥, m4] true [m5, m2, ⊥, m4] [⊥, m2, ⊥, m4] f alse Table 2: Illustrate the subsumed function S N U S
Using Table 2 we first illustrate the NUS subsumed function (S N U S ). In the first row, given two cache states cs 1 = [⊥, m2, ⊥, m4] and cs 2 = [m5, m2, ⊥, m4], S N U S (cs 1 , cs 2 ) = true. This shows the case when cs 1 is subsumed by a cs 2 . In the second row, given two cache states

CS 1 CS 2 CS 1 ∪ CS 2 J N U S (CS 1 , CS 2 ) {[⊥, m2, ⊥, m4], [m5, m6, m7, m8]} {[m5, m2, ⊥, m4], [m5, m6, m7, m8]} {[⊥, m2, ⊥, m4], [m5, m2, ⊥, m4], [m5, m6, m7, m8]} {[⊥, m2, ⊥, m4], [m5, m6, m7, m8]} Table 3: Illustrate the join function J N U S cs 1 = [m5, m2, ⊥,
m4] and cs 2 = [⊥, m2, ⊥, m4], S N U S (cs 1 , cs 2 ) = f alse. This shows the case when cs 1 is not subsumed by cs 2 .

Using Table 3, we illustrate the NUS join function. Given two sets of cache states

CS 1 = {[⊥, m2, ⊥, m4], [m5, m6, m7, m8]} and CS 2 = {[m5, m2, ⊥, m4], [m5, m6, m7, m8]}, CS 1 ∪CS 2 = {[⊥, m2, ⊥, m4], [m5, m2, ⊥, m4], [m5, m6, m7, m8]}. As illustrated in first row of Table 2, cache state [⊥, m2, ⊥, m4] is subsumed by [m5, m2, ⊥, m4]. Thus, J N U S (CS 1 , CS 2 ) = {[m5, m2, ⊥, m4], [m5, m6, m7, m8]}.

The NUS transfer function

A transfer function described how a reaching cache state of a basic block is transformed into a leaving cache state, after executing the instructions in the basic block. E.g., in Figure 3, the reaching cache state of block B2 is cs = [m1, m2, m3, m4] and after execution, where the instructions of the block as described by BI(B2) = [m5, ∓, ∓, ∓], the leaving cache state of B2 is cs = [m5, m2, m3, m4]. This transformation can be described as follows. First, if a block b does not have an instructions mapped to a cache line c i (BI(b)[i] = ∓), then after execution of the block, the contents of the cache corresponding to that cache line c i remains the same. E.g., basic block B2 has no instruction mapped to the cache line c 1 , (BI(B2) [START_REF]MicroBlaze Processor Reference Guide[END_REF] = ∓). Thus, after execution, the leaving cache state has the same instruction as the reaching cache state cs [START_REF]MicroBlaze Processor Reference Guide[END_REF] = m2 = cs [START_REF]MicroBlaze Processor Reference Guide[END_REF]. Secondly, if a block has an instruction mapped to a cache line (BI(b)[i] = ∓), then, after execution of the block, the content of the cache corresponding to that cache line is changed to the instruction executed by the block. E.g., basic block B2 has the instruction m5 mapped to the cache line c 0 , (BI(B2)[0] = ∓). Thus, after execution, the leaving cache state has the instruction m5, cs = m5 = BI(B2) [0] . The transfer function, T N U S , formalises this transformation as follows. For the cache line c 1 , block b has no instruction mapped to cache line c 1 (BI(b) [START_REF]MicroBlaze Processor Reference Guide[END_REF] = ∓). Thus, the instruction m2 on cache line c 1 in cs (m2 = cs [START_REF]MicroBlaze Processor Reference Guide[END_REF]), is copied to the cache line c 1 of the leaving cache state cs i.e., cs [START_REF]MicroBlaze Processor Reference Guide[END_REF] = m2 = cs [START_REF]MicroBlaze Processor Reference Guide[END_REF]. Similarly, block b has no instructions mapped to cache lines c 2 and c 3 , resulting in cs [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] = m3 = cs [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] and cs [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = m4 = cs [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]. Thus, given a block b, with BI(b) = [m5, ∓, ∓, ∓] and a reaching cache state cs = [m1, m2, m3, m4],

c i ∈ C where i ∈ [0, N -1], cs [i] = cs[i] : if BI(b)[i] = ∓ BI(b)[i] : otherwise
c 0 c 1 c 2 c 3 cs = [m1 m2 m3 m4] BI(b) = [m5 ∓ ∓ ∓] T N U S (b, cs) = cs = [m5 m2 m3 m4]
T N U S (b, cs) = cs = [m5, m2, m3, m4].
The transfer function, as defined in Definition 8, computes a leaving cache state for a basic block given a reaching cache state. During cache analysis, a block may have a set of reaching cache states. E.g., in Figure 3, block B8 has two reaching cache states, RCS B8 = {[m5, m2, m3, m4], [m5, m6, m7, m8]}. Thus, we extend the transfer function to compute a set of leaving cache states for a given set of reaching cache states for a block. [m5, m2, m3, m4] and

cs 2 = [m5, m6, m7, m8]. In this case, T N U S (B8, {cs 1 , cs 2 }) = {T N U S (B8, cs 1 )}∪ {T N U S (B8, cs 2 )}. In this example, T N U S (B8, cs 1 ) = [m5, m6, m3, m4] and T N U S (B8, cs 2 ) = [m5, m6, m3, m4]. Thus, T N U S (B8, {cs 1 , cs 2 }) = {[m5, m6, m3, m4]} ∪ {[m5, m6, m3, m4]} = {[m5, m6, m3, m4]}

Fixed point computation

As described in Definition 6, the cache analysis problem consists of two sub problems. The first sub problem is the computation of all reaching cache states for every block b ∈ B. The NUS approach [START_REF] Negi | Accurate Estimation of Cache-Related Preemption Delay[END_REF] solves this problem using a fixed point computation algorithm presented in Algorithm 1. We will present the NUS solution to the second sub problem following the fixed point algorithm (Algorithm 1). if b = b0 then 5:

Algorithm 1 Fixed point computation for the NUS approach

RCS i b 0 = {cs } 6:
else 7:

RCS i b = {cs ⊥ } 8:
end if 9: end for 10: repeat 11:

{Compute the set of leaving cache states for all blocks for iteration i} 12:

for each b ∈ B do 13:

LCS i b = TNUS(b, RCS i b ) 14:
end for 15:

i = i + 1; {Next iteration} 16: {Compute RCS} 17:
for each b ∈ B do

18: if b = b0 then 19: RCS i b = {cs } 20:
else 21:

RCS i b = ∅ 22:
for each LCS i b , where (b , b) ∈ E do 23:

RCS i b = JNUS(RCS i b , LCS i-1 b ) 24:
end for 25:

end if

26:

end for

27: until ∀b ∈ B, RCS i b = RCS i-1 b {Termination condition} 28: return RCS i b for all b ∈ B
In Algorithm 1, we first initialise the reaching cache states for all blocks (lines 3 to 9, Algorithm 1). Since we assume that initially the state of the cache is empty, on line 5 for the initial block b 0 we set its reaching as RCS i b0 = {cs }. Here, the notation RCS i b represents the reaching cache states of block b in iteration i. E.g., RCS 1 b0 represents the reaching cache states of block b 0 for iteration 1. For rest of the blocks, the execution of the CFG will impact the state of the cache, the state of the cache is unknown. Thus, on line 7, we set their reaching cache states as RCS 1 b = {cs ⊥ }. After initialisation, we compute the leaving cache states of each block, on lines 11 to 14. We apply the transfer function T N U S to every block and its corresponding reaching cache states.

The iteration index (i) is incremented (line 15) to signal the start of the next iteration. Next, on lines 16 to 26, the reaching cache states of each block are computed. For the initial block b 0 , we know that the reaching cache state is always empty. Thus, on line 19, we always set its reaching as RCS i b0 = {cs }. For rest of the blocks, on lines 22 to 24, the reaching cache states are computed by looking at the leaving cache states of the predecessors (b ) of the block b and using the NUS join function.

The iterative process, repeat-until loop on lines 10 to 27, is repeated until a fixed point is Inria reached, i.e., if two consecutive iterations have the same sets of reaching cache states for all blocks (line 27).

Illustration of the fixed point algorithm

We illustrate the above fixed-point algorithm using the Figure 6. The CFG and the mapping of the instructions to cache lines are presented in Figure 6(a) and Figure 6(b), respectively. These are reproduced from Figure 2. Figure 6(c) presents a table showing the reaching and leaving cache states for all blocks, during each iteration of the algorithm.

We first initialise the reaching cache states for all blocks (lines 3 to 9). For the CFG in Figure 6(a), the initial block is b 0 is B1. Since we assume that initially the state of the cache is empty, on line 5, we set RCS 1 B1 as {[ , , , ]}. For rest of the blocks, on line 7, the state of the cache is unknown. Thus, we set their reaching cache states as {[⊥, ⊥, ⊥, ⊥]}.

After initialisation, to compute the leaving cache states of each block, we apply the transfer function T N U S (lines 11 to 14). For example, in iteration 1

(i = 1), LCS 1 B1 = T N U S (B1, RCS 1 B1 ) = T N U S (B1, {[ , , , ]}) = {[m1, m2, m3, m4]}.
For block B2, which has one instruction m5 that is mapped to line c 0 , the leaving cache states

LCS 1 B2 = T N U S (B2, {[⊥, ⊥, ⊥, ⊥]}) = {[m5, ⊥, ⊥, ⊥]}.
Similarly, the leaving cache states (column 4) for rest of the blocks are computed for iteration 1 as shown in Figure 6(c).

The iteration index (i) is incremented (line 15) to signal the start of the next iteration (i = 2). Next, the reaching cache states of each block, for iteration i = 2, are computed (lines 16 to 26). For the initial block B1, we know that the reaching cache state is always cs . Thus, on line 19, we set its reaching cache state as RCS 2 B1 = {cs }. For rest of the blocks, on lines 22 to 24, the reaching cache states are computed by looking at the leaving cache states of the predecessors (b ) of the block b and using the NUS join function. E.g., the predecessors of B2 are B1 and B9, b ∈ {B1, B9}, and from the previous iteration

(i = 1) the LCS 1 B1 = {[m1, m2, m3, m4]} and LCS 1 B9 = {[⊥, ⊥, ⊥, m8]}.
The process for computing RCS 2 B2 is as follows.

1. Initialise RCS 2 B2 = ∅ (line 21). 2. Using the NUS join function we process the LCS of each predecessor block (B1, B9), on lines 22 to 24, one at a time (in no particular order). For illustration we will first analyse LCS 1 B1 followed by LCS 1 B9 as follows.

RCS 2 B2 = J N U S (RCS 2 B2 , LCS 1 B1 ) = J N U S (∅, {[m1, m2, m3, m4]}) = {[m1, m2, m3, m4]} RCS 2 B2 = J N U S (RCS 2 B2 , LCS 1 B9 ) = J N U S ({[m1, m2, m3, m4]}, {[⊥, ⊥, ⊥, m8]}) = {[m1, m2, m3, m4], [⊥, ⊥, ⊥, m8]}
The iterative process, repeat-until loop on lines 10 to 27, is repeated until a fixed point is reached, i.e., if two consecutive iterations have a same sets of reaching cache states for all blocks (line 27). For our example, it happens at the 9 th iteration, where the same sets of reaching cache states are computed for all blocks. As a result, the reaching cache states of the 9 th iteration represents all the possible reaching cache states of the program.

Note that during the first iteration, we assumed the reaching cache states for blocks B2 to B9 as unknown ({[⊥, ⊥, ⊥, ⊥]}), but when we reach the fixed-point, all the unknown cache states are resolved.

Finally, using the functions wmc(b, RCS 9 b ) and bmc(b, RCS 9 b ) (presented in Definitions 4 and Definition 5), the number of cache misses in the worst and the best case is computed. E.g., , m6, m3, m4]. Then, mc (B8, [m5, m2, m3, m4]) = 1 and mc (B8, [m5, m2, m3, m4]) = 2. Thus, wmc(B8, RCS B 8 9 ) = 2 andbmc(B8, RCS B 8 9 ) = 1. In summary, we have solved the first sub problem of cache analysis (Definition 6) using the fixed-point computation (Algorithm 1). For the second sub problem (Definition 6), we compute the number of cache misses for the worst and the best case using Definitions 4 and Definition 5.

B1: m1 m2 m3 m4 B2: m5 B3: m1
B4: m3 m4 B5: m2 B6: m2 m3 m4 B7: m6 m7 m8
B8: m3 m4 m6 B9: m8 (a) Control flow graph Cache Instructions line c 0 m1,m5 c 1 m2,m6 c 2 m3,m7 c 3 m4,m8 (b) Instructions to cache line mapping Iteration Block Reaching Cache Leaving Cache (i) (b) States (RCS i b ) States (LCS i b ) 1 B1 {[ , , , ]} {[m1, m2, m3, m4]} B2 {[⊥, ⊥, ⊥, ⊥]} {[m5, ⊥, ⊥, ⊥]} B3 {[⊥, ⊥, ⊥, ⊥]} {[m1, ⊥, ⊥, ⊥]} B4 {[⊥, ⊥, ⊥, ⊥]} {[⊥, ⊥, m3, m4]} B5 {[⊥, ⊥, ⊥, ⊥]} {[⊥, m2, ⊥, ⊥]} B6 {[⊥, ⊥, ⊥, ⊥]} {[⊥, m2, m3, m4]} B7 {[⊥, ⊥, ⊥, ⊥]} {[⊥, m6, m7, m8]} B8 {[⊥, ⊥, ⊥, ⊥]} {[⊥, m6, m3, m4]} B9 {[⊥, ⊥, ⊥, ⊥]} {[⊥, ⊥, ⊥, m8]} 2 B1 {[ , , , ]} {[m1, m2, m3, m4]} B2 {[m1, m2, m3, m4], [m1, ⊥, ⊥, m8]} {[m5, m2, m3, m4], [m5, ⊥, ⊥, m8]} B3 {[m5, ⊥, ⊥, ⊥]} {[m1, ⊥, ⊥, ⊥]} B4 {[m1, ⊥, ⊥, ⊥]} {[m1, ⊥, m3, m4]} B5 {[m1, ⊥, ⊥, ⊥], [⊥, ⊥, m3, m4]} {[m1, m2, ⊥, ⊥] [⊥, m2, m3, m4]} B6 {[m5, ⊥, ⊥, ⊥]} {[m5, m2, m3, m4]} B7 {[m5, ⊥, ⊥, ⊥]} {[m5, m6, m7, m7]} B8 {[⊥, m2, m3, m4], [⊥, m6, m7, m8]} {[⊥, m6, m3, m4]} B9 {[⊥, m2, ⊥, ⊥], [⊥, m6, m3, m4]} {[⊥, m2, ⊥, m8], [⊥, m6, m3, m8]} . . . . . . . . . . . . 8 B1 {[ , , , ]} {[m1, m2, m3, m4]} B2 {[m1, m2, m3, m4], [m1, m2, m3, m8], {[m5, m2, m3, m4], [m5, m2, m3, m8], [m5, m6, m3, m8]} [m5, m6, m3, m8]} B3 {[m5, m2, m3, m4], [m5, m2, m3, m8], {[m1, m2, m3, m4], [m1, m2, m3, m8], [m5, m6, m3, m8]} [m1, m6, m3, m8]} B4 {[m1, m2, m3, m4], [m1, m2, m3, m8] {[m1, m2, m3, m4], [m1, m6, m3, m4]} [m1, m6, m3, m8]} B5 {[m1, m2, m3, m4], [m1, m2, m3, m8], {[m1, m2, m3, m4], [m1, m2, m3, m8]} [m1, m6, m3, m8], [m1, m6, m3, m4]} B6 {[m5, m2, m3, m4], [m5, m2, m3, m8], {[m5, m2, m3, m4]} [m5, m6, m3, m8]} B7 {[m5, m2, m3, m4], [m5, m2, m3, m8], {[m5, m6, m7, m8]} [m5, m6, m3, m8]} B8 {[m5, m2, m3, m4], [m5, m6, m7, m8]}, {[m5, m6, m3, m4]} B9 {[m1, m2, m3, m4], {[m1, m2, m3, m8], [m1, m2, m3, m8], [m5, m6, m3, m4]} [m5, m6, m3, m8]} 9 B1 {[ , , , ]} {[m1, m2, m3, m4]} B2 {[m1, m2, m3, m4], [m1, m2, m3, m8], [m5, m6, m3, m8]} B3 {[m5, m2, m3, m4], [m5, m2, m3, m8], [m5, m6, m3, m8]} B4 {[m1, m2, m3, m4], [m1, m2, m3, m8] [m1, m6, m3, m8]} B5 {[m1, m2, m3, m4], [m1, m2, m3, m8], [m1, m6, m3, m8], [m1, m6, m3, m4]} B6 {[m5, m2, m3, m4], [m5, m2, m3, m8], [m5, m6, m3, m8]} B7 {[m5, m2, m3, m4], [m5, m2, m3, m8], [m5, m6, m3, m8]} B8 {[m5, m2, m3, m4], [m5, m6, m7, m8]}, B9 {[m1, m2, m3, m4], [m1, m2, m3, m8], [m5, m6, m3, m4]} (

The Absint approach

In the Absint approach [START_REF] Ferdinand | Cache Behavior Prediction by Abstract Interpretation[END_REF], the notion of cache states is different from that of the NUS approach. We first describe the notion of abstract cache states used during the Absint approach.

Abstract cache states

An abstract cache state describes the possible combination of instructions in the cache at some instance in time. It is described as a vector [set 0 , set 1 , . . . , set N -1 ] where each set i represents a set of instructions, and the set contains a possible instruction contained in cache line c i ∈ C of a cache state.

For the CFG shown in Figure 2(a), when the program starts executing, we assume the cache to be empty. This is represented as

[{ }, { }, { }, { }].
Instructions are loaded into the cache as the basic blocks are executed (starting from the initial block). E.g., After executing the basic block B1 the abstract cache state is [{m1}, {m2}, {m3}, {m4}].

Generally, the status of the cache may be unknown when a block is being analysed. In the Absint approach, we use the symbol ⊥ to represent an unknown instruction in a cache line. E.g., acs ⊥ = [{⊥}, {⊥}, {⊥}, {⊥}] represents the status of every cache line is unknown. This notion of unknown cache state is used during the cache analysis and is explained later.

We now define the abstract cache states.

Definition 10 (Abstract cache state). Given a cache model CM = I, C, CI, G, BI , an abstract cache state acs ⊆ (2 I∪{ ,⊥} ) N , can be represented as a vector [inst 0 , inst 1 , . . . , inst N -1 ] where each element acs[i] represents a set of possible instructions in cache line c i . Further, we restrict cache states such that, for any

i ∈ [0, N -1], acs[i] ⊆ CI(i) ∪ { , ⊥}. We denote acs = [{ }, { }, . . . , { }]
as the empty cache state, where all the elements of acs are { }. Similarly, we define acs ⊥ = [{⊥}, {⊥}, . . . , {⊥}], where all the elements of acs are {⊥}. Also, the set of all possible abstract cache states are referred to as ACS.

Before we illustrate abstract cache states, we introduce two key terms essential to cache analysis. For any basic block b, an abstract reaching cache state represents the abstract state of the cache prior to the execution of b. Abstract leaving cache state represents the abstract state of the cache after the execution of the basic block. We denote the abstract reaching cache state B2: m5 The abstract leaving cache state of B1 is also the abstract reaching cache state of B2, arcs B2 = alcs B1 . Block B2 has only one instruction m5, and is mapped to cache line c 0 . Thus, the previous instruction in line c 0 will be replaced by m5. Since the arcs B2 = [{m1}, {m2}, {m3}, {m4}], after executing the instructions in B2, the resulting abstract leaving cache state alcs B2 = [{m5}, {m2}, {m3}, {m4}]. Now, the control reaches a branch due to which, it is possible to execute either block B6 or block B7. In this case, arcs B6 = alcs B2 = arcs B7 . After executing blocks B6 or B7, the state of the cache is either [{m5}, {m2}, {m3}, {m4}] or [{m5}, {m6}, {m7}, {m8}].

B6: m2 m3 m4 B7: m6 m7 m8
B8: m3 m4 m6 c0 {m5} c1 {m6} c2 {m7} c3 {m8} c0 {m5} c1 {m6, m2} c2 {m7, m3} c3 {m8, m4} c0 { } c1 { } c2 { } c3 { } c0 {m1} c1 {m2} c2 {m3} c3 {m4} c0 {m5} c1 {m2} c2 {m3} c3 {m4} c0 {m5} c1 {m2} c2 {m3} c3 {m4} c0 {m5} c1 {m6} c2 {m3} c3 {m4}
Block B8 has two incoming edges: from blocks B6 and B7. To compute arcs B8 , we need to join alcs B6 and alcs B7 . In this case, the join function is a pair-wise union over the vector elements. Thus, arcs

B8 [i] = alcs B6 [i]∪alcs B7 [i], resulting in arcs B8 = [{m5}, {m2, m6}, {m3, m7}, {m4, m8}]. After execution of block B8, the resulting leaving cache state is [{m5}, {m6}, {m3}, {m4}].

The Absint join function

The Absint join function computes the abstract reaching cache state of a basic block when the block has more than one incoming edges. E.g., in Figure 7, the abstract reaching cache state of Block B8 has two incoming edges: from blocks B6 and B7. To compute arcs B8 we need to join alcs B6 and alcs B7 . It is possible that during the computation of the abstract reaching cache state of a block b, we may need to join two abstract leaving cache states that contain unknown instructions for some cache lines. E.g., alcs 1 = [{m1}, {⊥}, {m2}, {⊥}] and alcs 2 = [{m1}, {⊥}, {⊥}, {⊥}]. The join function could be described as an union over the abstract reaching cache states, i.e., arcs b = alcs 1 ∪ alcs 2 = [{m1}, {⊥}, {m2, ⊥}, {⊥}]. However, as described in Section 4.1, in the Absint approach an unknown instruction ⊥ is subsumed by any instruction. E.g., [{m1}, {⊥}, {m2, ⊥}, {⊥}] becomes [{m1}, {⊥}, {m2}, {⊥}]. This join Inria function for the Absint approach is defined in Definition 11.

Definition 11 (Absint join function). We define the join function J Absint : ACS ×ACS → ACS where for any two abstract cache states acs 1 ∈ ACS and acs 2 ∈ ACS, J Absint (acs 1 , acs 2 ) = acs 3 where for all cache lines c i ∈ C where i ∈ [0, N -1]

acs 3 [i] =    acs 1 [i] : if acs 2 [i] = ⊥ acs 2 [i] : if acs 1 [i] = ⊥ acs 1 [i] ∪ acs 2 [i] : otherwise Given two abstract cache states acs 1 = [{⊥}, {m2}, {m3}, {⊥}] and acs 2 = [{m5}, {m6}, {m7}, {⊥}], then, J Absint (acs 1 , acs 2 ) = [{m5}, {m2, m6}, {m3, m7}, {⊥}].
The union of sets that correspond to the same cache lines.

The Absint transfer function

The Absint transfer function describes how an abstract reaching cache state of a basic block is transformed into an abstract leaving cache state, after executing the instructions in the basic block. E.g., in Figure 7, the abstract reaching cache state of block B2 is arcs B2 = [{m1}, {m2}, {m3}, {m4}] and after the execution of block B2, where the instructions of the block is described by [{m5}, {m2}, {m3}, {m4}]. This transformation can be described as follows. Firstly, if a block b does not have an instructions mapped to a particular cache line c i (BI(b)[i] = ∓), then after execution of the block, the contents of the cache corresponding to that cache line remains the same. E.g., basic block B2 has no instruction mapped to the cache line c 1 , (BI(B2) [START_REF]MicroBlaze Processor Reference Guide[END_REF] = ∓), thus, after execution, the abstract leaving cache state has the same set of instructions as in the abstract reaching cache state alcs B2 [START_REF]MicroBlaze Processor Reference Guide[END_REF] = {m2} = arcs B2 . Secondly, if the block has an instruction mapped to a particular cache line (BI(b)[i] = ∓), then, after execution of the block, the content of the cache corresponding to that cache line is changed to the instruction executed by the block. E.g., basic block B2 has the instruction m5 mapped to the cache line c 0 , (BI(B2)[0] = ∓), thus, after execution, the abstract leaving cache state has the instruction m5, alcs B2 [0] = {m5} = {BI(B2)[0]} . The transfer function, T Absint , formalises this transformation as follows. For cache line c 0 , block b executes an instruction m5 on cache line c 0 (BI(b)[0] = m5). Thus, irrespective of the reaching cache state, the leaving cache (acs ) contains only the instruction m5 on its cache line c 0 , i.e., cs

BI(B2) = [m5, ∓, ∓, ∓], the abstract leaving cache state of B2 is alcs B2 =
acs [i] = acs[i] : if BI(b)[i] = ∓ BI(b)[i] : otherwise c 0 c 1 c 2 c 3 acs = [{m1, m5} {m2} {m3} {m4, m8}] BI(b) = [m5 ∓ ∓ ∓] T Absint (b, acs) = acs = [{m5} {m2} {m3} {m4, m8}]
[0] = {m5} = {BI(b)[0]}.
For the cache line c 1 , block b has no instruction mapped to cache line c 1 (BI(b) [START_REF]MicroBlaze Processor Reference Guide[END_REF] = ∓). Thus, the instructions set {m2} on cache line c 1 in acs (cs [START_REF]MicroBlaze Processor Reference Guide[END_REF] = {m2}), is copied to the cache line c 1 of the leaving cache state acs i.e., acs [START_REF]MicroBlaze Processor Reference Guide[END_REF] = {m2} = acs [START_REF]MicroBlaze Processor Reference Guide[END_REF]. Similarly, block b has no instructions mapped to cache lines c 2 and c 3 , resulting in acs [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] = {m3} = cs [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] and acs [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = {m4, m8} = acs [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]. Thus, given block b, with BI(b) = [m5, ∓, ∓, ∓] and a reaching cache state acs = [{m1, m5}, {m2}, {m3}, {m4, m8}], T Absint (b, acs) = acs = [{m5}, {m2}, {m3}, {m4, m8}].

Fixed-point computation

Cache analysis starts by the computation of abstract reaching cache state for every block b ∈ B. The Absint approach [START_REF] Ferdinand | Cache Behavior Prediction by Abstract Interpretation[END_REF] solves this problem using a fixed-point computation algorithm presented in Algorithm 2.

In Algorithm 2, we first initialise the abstract reaching cache states for all blocks (lines 3 to 9, Algorithm 2). Since we assume that initially the state of the cache is empty, on line 5 for the initial block b 0 we set its reaching as arcs 1 b0 = {acs }. Here, the notation arcs i b represents the abstract reaching cache state of block b in iteration i. E.g., arcs 1 b0 represents the reaching cache states of block b 0 for iteration 1. For the rest of the blocks, the execution of the CFG will impact the state of the cache, the state of the cache is unknown. Thus, on line 7, we set their reaching cache states as arcs 1 b = {acs ⊥ }. After initialisation, we compute the abstract leaving cache states of each block, on lines 11 to 14. We apply the transfer function T U oA to every block and its corresponding abstract reaching cache states.

The iteration index (i) is incremented (line 15) to signal the start of the next iteration. Next, on lines 16 to 26, the abstract reaching cache states of each block are computed. For the initial block b 0 , we know that the abstract reaching cache state is always empty. Thus, on line 19, we always set its reaching as arcs i b0 = {acs }. For rest of the blocks, on lines 22 to 24, the reaching cache states are computed by looking at the leaving cache states of the predecessors (b ) of the block b and using the Absint join function.

The iterative process, repeat-until loop on lines 10 to 27, is repeated until a fixed point is reached, i.e., if two consecutive iterations have the same sets of abstract reaching cache states for all blocks (line 27). for each b ∈ B do 13:

alcs i b = T Absint (b, arcs i b ) 14:
end for 15:

i = i + 1; {Next iteration} 16:
{Compute arcs } 17:

for each b ∈ B do We illustrate the fixed-point algorithm using the Figure 9. The CFG and the mapping of the instructions to cache lines are presented in Figure 9(a) and Figure 9(b) respectively. Figure 9(c) presents a table showing the abstract reaching and abstract leaving cache states for all blocks, during each iteration of the algorithm. We first initialise the abstract reaching cache states for all blocks (lines 3 to 9). For the CFG in Figure 9(a), the initial block is b 0 is B1. Since we assume that initially the state of the cache is empty, we set arcs 1

B1 as acs = [{ }, { }, { }, { }].
For the rest of the blocks, the state of the cache is unknown. Thus, we set their reaching cache states as acs ⊥ = [{⊥}, {⊥}, . . . , {⊥}].

After initialisation, to compute the abstract leaving cache state of each block, we apply the transfer function T Absint (lines 11 to 14). For example, in iteration 1 (i = 1), alcs 1 {m1}, {m2}, {m3}, {m4}]. For block B2, which has one instruction m5 that is mapped to line c 0 , the leaving cache states , {⊥}, {⊥}]. Similarly, the leaving cache states (column 4) for rest of the blocks are computed for iteration 1 as shown in Figure 9(c).

B1 = T Absint (B1, arcs 1 B1 ) = T Absint (B1, [{ }, { }, { }, { }]) = [
alcs 1 B2 = T N U S (B2, [{⊥}, {⊥}, {⊥}, {⊥}]) = [{m5}, {⊥}
The iteration index (i) is incremented (line 15) to signal the start of the next iteration (i = 2).

Inria

Next, the abstract reaching cache states of each block,for iteration i = 2, are computed (lines 16 to 26). For the initial block B1, we know that the abstract reaching cache state is always acs . Thus, on line 19, we always set its abstract reaching cache state as RCS 2 B1 = {cs }. For rest of the blocks, on lines 22 to 24, the reaching cache states are computed by looking at the abstract leaving cache states of the predecessors (b ) of the block b and using the Absint join function. E.g., the predecessors of B2 are B1 and B9, b ∈ {B1, B9}, and from the previous iteration (i = 1) the alcs 1 B1 = [{m1}, {m2}, {m3}, {m4}] and alcs Using the Absint join function we process the alcs of each predecessor block (B1, B9), on lines 22 to 24, on at a time (in no particular order). For illustration we will first analyse alcs 1 B1 followed by alcs 1 B9 as follows.

arcs 2 B2 = J U oA (arcs 2 B2 , alcs 1 B1 ) = J U oA ([∅, ∅, . . . , ∅], [{m1}, {m2}, {m3}, {m4}]) = {[{m1}, {m2}, {m3}, {m4}]} arcs 2 B2 = J U oA (arcs 2 B2 , alcs 1 B9 ) = J U oA ([{m1}, {m2}, {m3}, {m4}], [{⊥}, {⊥}, {⊥}, {m8}]) = {[{m1}, {m2}, {m3}, {m4, m8}]}
The iterative process, repeat-until loop on lines 10 to 27, is repeated until a fixed point is reached, i.e., if two consecutive iterations have a same set of abstract reaching cache state for all blocks (line 27). For our example, it happens in the 6 th iteration, where the same set of abstract reaching cache states are computed for all blocks. As a result, the reaching cache states of the 6 th iteration represents all the possible abstract reaching cache states of the program. Note that while the NUS approach reached a fixed point after 9 iterations, the Absint approach achieved a fixed point after 6 iterations, when applied over the same example.

Also, note that during the first iteration, we assumed the reaching cache states for blocks B2 to B9 as unknown ( [{⊥}, {⊥}, . . . , {⊥}]), but when we reach the fixed-point, all the unknown cache states are resolved.

Thus, we have presented how to computes all possible abstract reaching cache states arcs for every block in a given cache model. However, to solve the first sub problem (Definition 6) which involves the computation all the possible reaching cache states (RCS) for every basic block in the given cache model, we need to translate the arcs in to corresponding RCS.

Mapping an abstract cache state to cache states

An abstract cache state (acs) contains the possible set of instructions that can be present in the line c i (acs [i]). If we simply compute the cross product of these sets, we can compute the set of all cache states. For example, given the arcs = [{m5}, {m2, m6}, {m3, m7}, {m8}], the cross product is,

{[m5, m2, m3, m8], [m5, m2, m7, m8], [m5, m6, m3, m8], [m5, m6, m7, m8]}
Using Definition 13, we define the function that describes the above mapping.

Definition 13 (Abstract cache state to cache states mapping). We define a mapping function M AP Absint : ACS → 2 CS where, for a given abstract reaching cache states acs ∈ ACS is,

M AP Absint (acs) = acs[0] × acs[1] × . . . × acs[N -1] RR n°8214
For example, given an arcs = [{m5}, {m2, m6}, {m3, m7}, {m8}], then

M AP Absint (arcs) = arcs[0] × arcs[1] × arcs[2] × arcs[3] = {m5} × {m2, m6} × {m3, m7} × {m8} = {[m5, m2, m3, m8], [m5, m2, m7, m8], [m5, m6, m3, m8], [m5, m6, m7, m8]}
By mapping an abstract cache sate to a set of cache states, we have solved the first sub problem (Definition 6) which involves the computation all the possible reaching cache states (RCS) for every basic block in the given cache model.

Calculating cache misses

The second sub problem of cache analysis (Definition 6) involves the computation of the number of cache misses for the best case and the worst case of every basic block. We present two solutions to this problem.

First, after translating arcs (computed using Algorithm 2) into RCS (as described in Definition 13), using the functions wmc and bmc (presented in Definitions 4 and Definition 5), the number of cache misses in the worst and the best case can be computed.

Second, the number of cache misses could be computed by directly analysing the abstract cache state arcs. An abstract cache state arcs describes the possible combination of instructions in the cache at some instance in time. arcs[i] describes the possible instructions that can be present on the cache line c i . For example, consider the abstract reaching cache state arcs = [{m5}, {m2, m6}, {m3, m7}, {m8}]. For the cache line c 1 , arcs [START_REF]MicroBlaze Processor Reference Guide[END_REF] = {m2, m6} describes that the cache either contains the instruction m2 or m6. BI(b)[i] represents the instruction that block b executes cache line c i . E.g., consider the block B8 with BI(B8) = [∓, m6, m3, m4]. Then, BI(B8) [START_REF]MicroBlaze Processor Reference Guide[END_REF] = m6 describes that block B8 needs the instruction m6 on the cache line c 1 . We now describe how to compute the number of cache misses for the worst case and the best case. Using Definitions 14 and 15, we define the functions that compute the number of cache misses for the worst and the best case for a block directly from an abstract (reaching) cache state. where,

Worst case analysis

wmiss i = 1 : if BI(b)[i] = ∓ and BI(b)[i] ∈ acs[i] 0 : otherwise

Illustration

Given a acs = [{m5}, {m2, m6}, {m3, m7}, {m8}] and BI(B8) = [∓, m6, m3, m4], using Fig- During a worst case analysis, for cache line c 0 , we do not have a cache miss, wmiss 0 = 0, because the block B8 does not have any instruction mapped to c 0 (BI (B8)[0] = ∓). For cache line c 1 , we have a cache miss, wmiss 1 = 1, because the block needs to execute m6 and it is not the only possible instruction in the cache ({BI(B8) [START_REF]MicroBlaze Processor Reference Guide[END_REF]} = {m6} = {m2, m6} = acs [START_REF]MicroBlaze Processor Reference Guide[END_REF]). Similarly, wmiss 2 = 0, because m3 is not the only possible instruction in the cache ({BI(B8) [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]} = {m3} = {m3, m7} = acs [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]). Finally, for the cache line c 3 , we have a cache miss, wmiss 3 = 1, because the block needs to execute m4, while the cache contains m8 ({BI(B8) [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]} = {m4} = {m8} = acs [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]). Thus, for the four cache lines, in the worst case, we get three misses (wmc Absint (B8, acs) = 0 + 1 + 1 + 1 = 3).

c i c 0 c 1 c 2 c 3 acs = [{m5} {m2, m6} {m3, m7} {m8}] BI(B8) = [ ∓ m6 m3 m4] wmiss i = 0 1 1 1 = 3 = wmc Absint (B8, acs) bmiss i = 0 0 0 1 = 1 = bmc Absint (B8, acs)
During a best case analysis, for cache line c 0 , we do not have a cache miss, bmiss 0 = 0, because the block B8 does not have any instruction mapped to c 0 (BI (B8)[0] = ∓). For cache line c 1 , we have a possible cache hit, wmiss 1 = 1, because the block needs to execute m6 and it is present in the set of possible instruction in the cache ({BI(B8) [START_REF]MicroBlaze Processor Reference Guide[END_REF]} = {m6} ∈ {m2, m6} = acs [START_REF]MicroBlaze Processor Reference Guide[END_REF]). Similarly, for the cache line c 1 , we have a possible cache hit wmiss 2 = 1, because m3 is present in the set of possible instruction in the cache ({BI(B8) [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]} = {m3} ∈ {m3, m7} = acs [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]). Finally, for the cache line c 3 , we have a cache miss, wmiss 3 = 1, because the block needs to execute m4 and the instruction is not in the cache ({BI(B8) [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]} = {m4} ∈ {m8} = acs [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]). Thus, for the four cache lines, in the best case, we get three misses (bmc Absint (B8, acs) = 0 + 0 + 0 + 1 = 1).

In summary, we have solved the first sub problem of cache analysis (Definition 6) using the fixed-point computation (Algorithm 2) and the abstract cache state to cache states mapping function (Definition 13). For the second sub problem (Definition 6), we define two solutions (directly over arcs, or indirectly by mapping to CS) to compute the number of cache misses for the worst and the best case.

Comparison between NUS and Absint approaches

In this section, using Table 4, we present a comparison between the NUS and the Absint approaches. For the example (presented in Figure 2), column 2 presents the number of iterations required for reaching the fixed point computation. Column 3 presents the reaching cache states for block B8 computed during the NUS approach, and the abstract reaching cache states for block B8 computed during the Absint approach. Finally, the number of cache misses in the worst case and the best case are presented in columns 5 and 6 respectively. Approaches for solving the cache analysis problem may be compared on the basis of precision and the analysis time.

Approach Ite.

RCSB8/arcsB8

Worst case Best case

NUS 9 [m5, m2, m3, m4] 2 1 [m5, m6, m7, m8] Absint 6 [{m5}, {m2, m6}, {m3, m7}, {m4, m8}] 3 0
Table 4: Comparing the precision between the NUS and the Absint approaches.

Precision

The NUS approach is more precise than the Absint approach, for both the worst case (2 < 3) and the best case (1 > 0) analysis.

Analysis time:

The NUS approach is slower than the Absint approach. It takes 9 iterations to reach the fixed point, while the Absint approach takes only 6 iterations.

In general, Precision and Analysis time are complementary opposite to each other, i.e., If an approach yields high precision it is most likely will have high analysis time, and vice versa. The Absint approach, abstracts the relation between the cache lines during the join function (Definition 11), by doing a pair-wise union over elements of abstract reaching cache states. This, reduces the precision of the analysis. In contrast, the NUS approach during the join function (Definition 7), accumulates all cache states and does not lose any precision, but is much slower than the Absint approach.

In general, due to the scalability, the Absint approach is more practical and adopted by industry for successfully analysing large programs. However, some applications could significantly gain from more precise analysis. We present this idea in Figure 11. The ideal cache analysis approach should be as closer to the desired region as possible. Using this as a objective, in Section 6 we present our new cache analysis approach.

In Table 5 we present a summary of the symbols and the definitions that are presented in this section.

Symbol/ Definition Description

Example

J N U S : 2 CS × 2 CS → 2 CS NUS join function CS 1 = {[m5, m2, m3, m4]} and CS 2 = {[m5, m6, m7, m8]}, J N U S (CS 1 , CS 2 ) = {[m5, m2, m3, m4], [m5, m6, m7, m8]} T N U S : B × 2 CS → 2 CS NUS transfer function cs 1 = [m5, m2, m3, m4], cs 2 = [m5, m6, m7, m8], RCS B8 = {cs 1 , cs 2 }, T N U S (B8, {cs 1 , cs 2 }) = {[m5,
) = [{m5}, {m2, m6}, {m3, m7}, {⊥}] T Absint : B × ACS → ACS Absint transfer func- tion BI(b) = [m5, ∓, ∓, ∓], acs = [{m1}, {m2}, {m3}, {m4}], T Absint (b, acs) = acs = [{m5}, {m2}, {m3}, {m4}] M AP Absint : ACS → 2 CS Abstract cache state to cache states mapping acs = [{m5}, {m2, m6}, {m3, m7}, {m8}], then M AP Absint (acs) = {[m5, m2, m3, m8], [m5, m2, m7, m8], [m5, m6, m3, m8], [m5, m6, m7, m8]} wmc Absint : B × ACS → N 0 Absint worst miss count acs = [{m5}, {m2, m6}, {m3, m7}, {m8}] and BI(B8) = [∓, m6, m3, m4] then, wmc Absint (B8, acs) = 0 + 1 + 1 + 1 = 3 bmc Absint : B × ACS → N 0 Absint best miss count acs = [{m5}, {m2, m6}, {m3, m7}, {m8}]
and BI(B8) = [∓, m6, m3, m4] then, bmc Absint (B8, acs) = 0 + 0 + 0 + 1 = 1

Table 5: Some of the symbols and the definitions presented in this section.

6 Proposed approach

Overview

The NUS approach (see Section 3) and the Absint approach (see Section 4) solve the cache analysis problem (Definition 6) by analysing all basic blocks in a single fixed point computation.

However, if we analyse only one block (called the reference block) at a time, we can ignore blocks that execute instructions which do not affect the precision (number of cache hits/misses) of the reference block. Secondly, we can abstract the instructions in the cache state w.r.t. the instructions executed by the reference block. This may significantly reduce the number of possible cache states, and may reduce the number of iterations required during cache analysis, resulting in faster analysis time compared to the NUS approach. These are the basis of our proposed approach. Importantly, our abstraction is unlike the Absint approach, and the precision is the same as the NUS approach. Our intuition for analysing each block individually is based on the following two observations. )[0] = ∓). Thus, we can ignore the instructions m1 and m5 that are executed by blocks B1 and B2. This leaves block B2 with its only instruction being mapped to the unrefereed cache line c 0 . Hence, B2 is vacuous, and can be removed from the graph. By reducing the number of cache lines to be analysed, and by removing vacuous blocks, we can perform more efficient (faster) analysis of a block. For example, given BI(B8) = [∓, m6, m3, m4] and BI(B1) = [m1, m2, m3, ∓], during the analysis of block B8 (reference block = B8 =b ref ), the instructions in block B1 can be abstracted as the vector [×, 1, 0, ∓], and is computed as follows:

1. The first element of the vector is × because the instruction is not of interest as the reference block does not have any instruction on cache line c 0 (BI (B8)[0] = ∓).

2. The second element of the vector is 1. This captures that for cache lines c 1 the instruction in B1 is different to the instruction in B8 (BI(B1) [START_REF]MicroBlaze Processor Reference Guide[END_REF] = m2 = m6 = BI(B8) [START_REF]MicroBlaze Processor Reference Guide[END_REF]).

3. The third element of the vector is 0. This captures that for cache lines c 2 the instruction in B1 is same as the instructions in B8 (BI(B8) [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] = m3 = BI(B1) [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]).

4. Finally, the fourth element of the vector is ∓. This captures that for cache lines c 3 there is no instruction in B1 (BI(B1) [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = ∓).

Inria

This abstraction reduces the number of instructions (|I|) in the CFG to just four values (×, ∓, 0, 1), which reduces the memory foot print and could reduces the analysis time. We refer to these four abstract instructions as relative instructions and the instructions (I) as concrete instructions.

An overview of the proposed approach is presented using Algorithm 3. In our approach, as explained earlier, we analyse each block individually. This is described using the for-loop on lines 1 to 8. For each reference block b ref in B, on line 2, we first reduce the CFG and compute relative instructions w.r.t the reference block (using Algorithm 44, explained later in Section 6.2). Due to the relative instructions, cache states also needs to be represented using relative instructions (explained later in Section 6.5). On line 3, using a fixed point computation, we compute all the possible reaching relative cache states of the reference block (using Algorithm 5, explained later in Section 6.5). Finally, on line 6 to 7, the number of cache misses in the worst/best case are computed (using Definitions 21 and 22, explained later in Section 6.5). We now present each of the algorithms and definition in detail.

Algorithm 3 Overview of the proposed approach

Reducing the CFG and abstracting the instructions

We now formalise Observations 1 and 2 using Algorithm 4. Given a cache model CM = I, C, CI, G, BI and the reference block b ref ∈ B, the objective of the algorithm is: [START_REF]MicroBlaze Processor Reference Guide[END_REF] to compute a new reduced graph G r = B r , b init , E r which contains only these blocks that are relevant for the analysis of block b ref (described in Observation 1) and, (2) to compute the function BI r which describes the relative instructions executed by the blocks in B r w.r.t b ref , referred as the relative instruction mapping function. The algorithm contains the following three steps.

Step 1: Initialise (lines 2 to 4). On line 2, we initialise G r to have the same content as G, i.e., same set of blocks (B r = B), initial block (b init ), edges (E r = E). On lines 3 to 4, we initialise the function BI r such that it does not contain any relative instructions for any block. For the example CFG (presented in Figure 2(a)), the graph G r is presented in Figure 12(a).

Step For the graph G r in Figure 12 This check is done on line 25. It is possible for the initial block (b init ) to be vacuous. However, if the initial block has more than one successors, removing the initial block may result in multiple initial blocks. Thus, to simplify the analysis, we do not remove the initial block even when it is vacuous (line 25).

If a block b 1 is vacuous, we first compute the predecessors (line 27) and the successors (line 28) of b 1 . Secondly, we remove the incoming edges to b 1 from each predecessor block (on lines 30 to 32) and, we remove the outgoing edges from b 1 to each successor block (on lines 33 to 35). Thirdly, we create a transition from each predecessor to each successor of b 1 . This is achieved using the nested loop on lines 37 to 41. Finally, on line 42, the vacuous block b 1 is removed.

For the graph shown in Figure 12 for each

c i ∈ C do 9: if (BI(b ref )[i] = ∓){not of interest} then 10: BI r (b 1 )[i] = × 11: end if 12: if (BI(b ref )[i] = BI(b 1 )[i]) {different instruction} then 13: BI r (b 1 )[i] = 1 14: end if 15: if (BI(b ref )[i] = BI(b 1 )[i]){same instruction} then 16: BI r (b 1 )[i] = 0 17: end if 18: if (BI(b 1 )[i] = ∓){no instruction} then 19: BI r (b 1 )[i] = ∓ 20:
end if 21:

end for 22: end for

P reds = {b 2 |b 2 → b 1 ∈ E r } 28: Succ = {b 2 |b 1 → b 2 ∈ E r } 29:
{Remove incoming and outgoing edges of b 1 } 30:

for each b 2 ∈ P reds do 31:

E r = E r \ {b 2 → b 1 } 32:
end for 33:

for each b 2 ∈ Succ do 34:

E r = E r \ {b 2 → b 1 } 35:
end for 36:

{Add new edge from each predecessor to each successor } 37:

for each b p ∈ P reds do 38:

for each b s ∈ Succ do 39:

E r = E r ∪ {b p → b s } 40:
end for 41:

end for 42:

B r = B r \ {b 1 } {Remove block b 1 } 43: end if 44: end for RR n°8214 B1 ci BI c0 m1 c1 m2 c2 m3 c3 m4 B2 ci BI c0 m5 c1 ∓ c2 ∓ c3 ∓ B3 ci BI c0 m1 c1 ∓ c2 ∓ c3 ∓ B4 ci BI c0 ∓ c1 ∓ c2 m3 c3 m4 B5 ci BI c0 ∓ c1 m2 c2 ∓ c3 ∓ B6 ci BI c0 ∓ c1 m2 c2 m3 c3 m4 B7 ci BI c0 ∓ c1 m6 c2 m7 c3 m8 B8 ci BI c0 ∓ c1 m6 c2 m3 c3 m4 B9 ci BI c0 ∓ c1 ∓ c2 ∓ c3 m8 (a) Graph G r after step 1 B1 ci BI BI r c0 m1 × c1 m2 1 c2 m3 0 c3 m4 0 B2 ci BI BI r c0 m5 × c1 ∓ ∓ c2 ∓ ∓ c3 ∓ ∓ B3 ci BI BI r c0 m1 × c1 ∓ ∓ c2 ∓ ∓ c3 ∓ ∓ B4 ci BI BI r c0 ∓ × c1 ∓ ∓ c2 m3 0 c3 m4 0 B5 ci BI BI r c0 ∓ × c1 m2 1 c2 ∓ ∓ c3 ∓ ∓ B6 ci BI BI r c0 ∓ × c1 m2 1 c2 m3 0 c3 m4 0 B7 ci BI BI r c0 ∓ × c1 m6 0 c2 m7 1 c3 m8 1 B8 ci BI BI r c0 ∓ × c1 m6 0 c2 m3 0 c3 m4 0 B9 ci BI BI r c0 ∓ × c1 ∓ ∓ c2 ∓ ∓ c3 m8 1 (b) Graph G b ref after step 2, given b ref = B8 B1: ci BI BI r c0 m1 × c1 m2 1 c2 m3 0 c3 m4 0 B4: ci BI BI r c0 ∓ × c1 ∓ ∓ c2 m3 0 c3 m4 0 B5: ci BI BI r c0 ∓ × c1 m2 1 c2 ∓ ∓ c3 ∓ ∓ B6: ci BI BI r c0 ∓ × c1 m2 1 c2 m3 0 c3 m4 0 B7: ci BI BI r c0 ∓ × c1 m6 0 c2 m7 1 c3 m8 1 B8: ci BI BI r c0 m1 × c1 m2 0 c2 m3 0 c3 m4 0 B9 ci BI BI r c0 ∓ × c1 ∓ ∓ c2 ∓ ∓ c3 m8 1 (c) Graph G b ref after step 3, given b ref = B8 (re- duced graph).
i c 0 c 1 c 2 c 3 BI(b 1 ) = [m1 m2 m3 ∓] BI(b ref ) = [ ∓ m6 m3 m4] BI r (b 1 ) = × 1 0 ∓ = =

Relative cache states

We describe the state of a cache using the notion of relative cache states. A relative cache state is described as a vector [inst r 0 , inst r 1 , . . . , inst r N -1 ], where each element inst r i is described w. • inst r i = represents that the cache does not contain any instruction i.e., it is empty. • inst r i = ⊥ represents that the cache has an unknown instruction. • inst r i = × represents that the instruction on this cache line is not of interest during the analysis of b ref .

Definition 16 (Relative cache state). Given a reference block b ref , a relative cache state cs r ∈ ({1, 0, , ⊥, ×}) N , is a vector [inst r 0 , inst r 1 , . . . , inst r N -1 ], where each element inst r i ∈ {1, 0, , ⊥, ×}. Also, the set of all possible relative cache states (w.r.t b ref ) is denoted as CS r .

Before we illustrate relative cache states, we introduce two key terms essential to cache analysis. For any basic block b, the reaching relative cache states represent the set of relative cache states prior to the execution of a basic block and the relative leaving cache states represent the set of cache states after the execution of the basic block. We denote the reaching relative cache states of a basic block b as RCS r b and the relative leaving cache states of a basic block b as LCS r b . Illustration A fragment of the reduced graph (Figure 12(c)) is presented in Figure 14. Using this graph we illustrate relative reaching and leaving cache states of a block. Given the reference block , m6, m3, m4] and the relative instruction mapping of each block (described by the function BI r ), we illustrate the relative cache state as we start executing the initial block B1. Initially, the cache is empty and the reference block does not have an instruction on cache line c 0 (BI r (b ref )[0] = ∓). Thus the instruction on cache line c 0 is not of interest (×) resulting in the initial cache state of [×, , , ], denoted as cs r . Note this initial cache state is unlike the NUS approach, where the initial state is represented using the vector [ , , , ]. In our approach, given the reference block b ref (in this case b ref = B8), we are only interested in the cache line c 1 , c 2 , c 3 . Thus, we ignore the cache state w.r.t cache line c 0 , as it does not affect the precision of the reference block. Also, by ignoring c 0 , allows for a memory efficient implementation. In this case, the relative cache state can be represented using a vector with only three elements, instead of four elements, saving 25% of memory.

b ref = B8 with BI(b ref ) = [∓
Start B1 ci BI r c0 × c1 1 c2 0 c3 0 B6 ci BI r c0 × c1 1 c2 0 c3 0 B7 ci BI r c0 × c1 0 c2 1 c3 1 B8 ci BI r c0 × c1 0 c2 0 c3 0 B9 ci BI r c0 × c1 ∓ c2 ∓ c3 1 c0 × c1 0 c2 1 c3 1 c0 × × c1 0 1 c2 1 0 c3 1 0 c0 × c1 0 c2 0 c3 1 c0 × c1 c2 c3 c0 × c1 1 c2 0 c3 0 c0 × c1 1 c2 0 c3 0 c0 × c1 0 c2 0 c3 0
After execution of block B1, where the relative instructions are described by BI r (B1) = [×, 1, 0, 0], cache lines c 1 , c 2 , c 3 will contain relative instructions 1, 0, 0. Hence after B1 executes, the relative cache state cs r = [×, 1, 0, 0]. Here, cs r [0] = × represents the instruction on cache line c 0 is not of interest. cs r [1] = 1 represents that the instruction in the cache is not m6, because BI(b ref ) [START_REF]MicroBlaze Processor Reference Guide[END_REF] = m6. cs r [2] = 0 represents that the instruction in the cache is m3, because BI(b ref ) [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] = m3. Similarly, cs r [3] = 0 represents the instruction in the cache is m4 (BI(b ref ) [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = m4).

The relative cache state cs r is the state of the cache prior to the execution of the basic block B1. Thus, RCS r B1 = {[×, , , ]} is the set of reaching relative cache states of block B1. Similarly, LCS r B1 = {[×, 1, 0, 0]} is the set of relative leaving cache states of block B1. Now, the control reaches a branch due to which, it is possible to execute either block B6 or block B7. In this case, RCS r B6 = LCS r B1 = RCS r B7 . After executing blocks B6 (or B7), the state of the cache is [×, 1, 0, 0] (or [×, 0, 1, 1]).

Block B8 has two incoming edges: from blocks B6 and B7. To compute RCS r B8 , we need to join LCS r B6 and LCS r B7 . In this case, the join function is a union over the set of relative cache states. Thus,

RCS r B8 = LCS r B6 ∪ LCS r B7 , resulting in RCS r B8 = {[×, 0, 1, 1], [×, 1, 0, 0]}.
The UoA join function is different to a simple union operator, due to its handling of unknown instructions (⊥). During the computation of the reaching relative cache states of a block b, we may need to join two leaving relative cache states that may contain unknown (⊥) instructions for some cache lines. E.g., LCS r 1 = {cs r 1 } where cs r

1 = [1, ⊥, ⊥, ⊥] and LCS r 2 = {cs r 2 } where cs r 2 = [1, ⊥, 0, ⊥].
In this case, given two relative cache states cs r 1 and cs r 2 , the cache state cs r 1 is subsumed by the cache state cs r 2 , if for all cache lines (c i ∈ C), when the relative instruction in cs r 2 is same as the instruction in cs r 1 (cs r

2 [i] = cs r 1 [i]) or, the relative instruction in cs r 1 is unknown Inria inst 2 N -1 ], after executing the relative instructions in the basic block b with BI r (b) = [inst b 0 , inst b 1 , . . . , inst b N -1 ]
. The transformation can be described using the following four cases: (1) If a block b does not have an instruction mapped to a cache line c i (inst b i = ∓), or (2) a cache line c i is not of interest (inst b i = ×) then after execution of the block, the contents of the cache corresponding to that cache line remains unchanged (inst 2 0 = inst 1 i ). ( 3) If a block b has the same (inst b i = 0), or (4) different (inst b i = 1) relative instruction, then after execution of the block, the content of the relative leaving cache is changed to the relative instruction executed by the block (cs r 2 [i] = inst b i ]). For example, given a reaching relative cache state cs r

1 = [×, 1, 1, 1] of block b, with BI r (b) = [×, ∓, 0, 0], the relative leaving cache state cs r 2 = [×, 1, 0, 0].
Here, for cache line c 0 the instruction in block b is not of interest (BI r (b)[0] = ×). Thus, the state of the cache is unchanged (cs r

2 [0] = × = cs r 1 [0]
). For cache line c 1 the block b does not have a relative instruction (BI r (b)[0] = ∓). Hence, the state of the cache is also unchanged (cs r 2 [START_REF]MicroBlaze Processor Reference Guide[END_REF] = 0 = cs r 1 [START_REF]MicroBlaze Processor Reference Guide[END_REF]). In contrast, for cache lines c 2 and c 3 , block b has relative instructions (BI r (b) [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] = 0 and BI r (b) [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = 0). Thus, the state of the cache is updated (cs r 2 [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] = 0 = BI r (b) [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] and cs r 2 [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = 0 = BI r (b) [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]). We now define the transfer function using Definition 18.

Definition 18 (UoA transfer function). The UoA transfer function T U oA : B × CS r → CS r where, for a given basic block b ∈ B and a relative cache state cs r 1 ∈ CS r ,

T U oA (b, cs r 1 ) = cs r 2
where for all cache lines [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = ∓) mapped to the cache lines. Thus, the content of the relative cache state is unchanged.

c i ∈ C where i ∈ [0, N -1], cs r 2 [i] = BI r (b)[i] : if (BI r (b)[i] = 0) ∨ (BI r (b)[i] = 1) cs r 1 [i] : otherwise Illustration c 0 c 1 c 2 c 3 cs r 1 = [1 0 1 0] BI r (b) = [∓ 1 0 ∓] T U oA (b, cs r 1 ) = cs r 2 = [1 1 0 0]
For the cache lines c 1 and c 2 , the relative instructions are 1 (BI r (b) [START_REF]MicroBlaze Processor Reference Guide[END_REF]) and 0 (BI r (b) [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]) respectively. Thus, the relative leaving cache state contains 1 on cache line c 1 (cs r 2 [START_REF]MicroBlaze Processor Reference Guide[END_REF] = BI r (b)[i]) and 0 on cache line c 2 (cs r 2 [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] = BI r (b) [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]). Hence, given a block b, with BI r (b) = [∓, 1, 0, ∓] and a reaching relative cache state cs r 1 = [1, 0, 1, 0], T U oA (b, cs r 1 ) = cs r 2 = [1, 1, 0, 0]. Given a reaching relative cache state of a basic block, the transfer function (Definition 18) computes its leaving relative cache state. During cache analysis, a block may have a set of Inria reaching relative cache states. E.g., in Figure 14, the block B8 has two reaching cache states, RCS r B8 = {[×, 0, 1, 1], [×, 1, 0, 0]}. Thus, we extend the transfer function to compute a set of relative leaving cache states for a given set of reaching relative cache states for any block.

Definition 19 (Extended UoA transfer function). We define the transfer function T U oA : B × 2 CS r → 2 CS r where, for a given basic block b ∈ B and a set of cache states CS r 1 ⊆ 2 CS r ,

T U oA (b, CS r 1 ) = CS r 2
where for all cache states cs r i ∈ CS r 1 is,

CS r 2 = |CS r 1 | i=1 {T U oA (b, cs r i )}
In Figure 14, block B8 has two reaching cache states

(RCS r B8 = {cs r 1 , cs r 2 }) where cs r 1 = [×, 0, 1, 1] and cs r 2 = [×, 1, 0, 0]. In this case, T U oA (B8, {cs r 1 , cs r 2 }) = {T U oA (B8, cs r 1 )}∪ {T U oA (B8, cs r
2 )}. In this example, T U oA (B8, cs r 1 ) = [×, 0, 0, 1] and also

T U oA (B8, cs r 2 ) = [×, 0, 0, 1]. Thus, T U oA (B8, {cs 1 , cs 2 }) = {[×, 0, 0, 1]} ∪ {[×, 0, 0, 1]} = {[×, 0, 0, 1]}.

Computing all possible reaching relative cache states of the reference block

The first step for cache analysis involves the computation of all possible reaching relative cache states of b ref (RCS r b ref ), using the fixed point computation algorithm presented in Algorithm 5. As illustrated in Figure 14, the initial state of the cache is empty(cs r ), and is based on the instructions of the reference block. Similarly, like the NUS and the Absint approaches, we must also introduce the unknown cache state (cs r ⊥ ), which is explained later during this algorithm. In general, the empty/unknown cache state is different for each b ref ∈ B. Thus, for a given reference block b ref , we first compute the empty cache state cs r , and unknown cache state cs r ⊥ on lines 2 to 8.

For each cache line c i , if the reference block b ref does not have an instruction (in this case, BI r (b ref ) = ×), then the cache state on c i is not of interest during the analysis of the reference block b ref . Thus, the relative instruction on cache line c i of cs r and cs r ⊥ is set to × (line 4). Otherwise (BI r (b ref ) = ×), on line 6, for cache line c i , the empty cache state is set to be (cs r [i] = ), and the unknown cache state is set to be ⊥ (cs r ⊥ [i] = ⊥). Using relative cache states cs r and cs r ⊥ , we initialise the reaching relative cache states for all blocks (lines 11 to 17). Since we assume that initially the state of the cache is empty, on line 13 for the initial block b init we set its reaching as RCS r 1 binit = {cs r }. Here, the notation RCS r i b represents the reaching relative cache states of block b in iteration i. E.g., RCS r 1 binit represents the reaching relative cache states of block b init for iteration 1. For rest of the blocks, the initial state of the cache is unknown. Thus, on line 15, we set their reaching cache states as {cs r ⊥ }. After initialisation, we compute the relative leaving cache states of each block, on lines 19 to 22. We apply the transfer function T U oA to every block and its corresponding reaching relative cache states.

The iteration index (i) is incremented (line 23) to signal the start of the next iteration. Next, on lines 25 to 34, the reaching relative cache states of each block are computed. For the initial block b init , we know that the reaching relative cache state is always empty. Thus, on line 27, we

if BI r (b ref )[i] = × then 4: cs r [i] = ×, cs r ⊥ [i] = ×

Inria

always set its reaching as RCS r i binit = {cs }. For rest of the blocks, we first initialise the reaching relative cache state as empty set (line 29), and on lines 30 to 32, the reaching cache states are computed by looking at the relative leaving cache states of the predecessors (b ) of the block b and using the UoA join function.

The iterative process, repeat-until loop on lines 18 to 35, is repeated until a fixed point is reached, i.e., if two consecutive iterations have the same sets of reaching relative cache states for all blocks (line 35).

Illustration of the fixed point algorithm

We describe the fixed point algorithm using the Figure 16. The reduced graph G r w.r.t the reference block, (b ref = B8) is presented in Figure 16(a). Figure 16(b) presents a table showing the reaching and leaving relative cache states for all blocks, during each iteration of the algorithm.

We first initialise the empty cache state cs r and the unknown cache state cs r ⊥ on lines 2 to 8. The reference block B8 does not have an instruction on cache line c 0 (BI r (b ref )(0) = ∓), and has an instruction for rest of the cache lines (c 1 , c 2 , c 3 ). Thus, we get cs r = [×, , , ] and

cs r = [×, ⊥, ⊥, ⊥].
Using relative cache states cs r and cs r ⊥ , we initialise the reaching relative cache states for all blocks (lines 11 to 17). For the CFG in Figure 16(a), the initial block (b init ) is B1. Since we assume that initially the state of the cache is empty, on line 13, we set RCS r i binit as {cs r } = {[×, , , ]}. For rest of the blocks, on line 7, the state of the cache is unknown. Thus, we set their reaching cache states as {cs r ⊥ } = {[×, ⊥, ⊥, ⊥]}, as presented during the first iteration in column 3 of Figure 16(b).

After initialisation, to compute the relative leaving cache states of each block, we apply the transfer function T U oA (lines 19 to 22). For example, in iteration 1, LCS r 1 B1 = T U oA (B1, RCS r 1 B1 ) = T U oA (B1, {[×, , , ]}) = {[×, 1, 0, 0]}. Similarly, the relative leaving cache states for rest of the blocks are computed.

The iteration index (i) is incremented (line 23) to signal the start of the next iteration (i = 2). Next, the reaching relative cache states of each block, for iteration i = 2, are computed (lines 25 to 34). For the initial block B1, we know that the reaching relative cache state is always cs r . Thus, on line 27, we set its reaching relative cache state as RCS r 2 B1 = {cs }. For the remaining blocks, on lines 29 to 32, the reaching relative cache states are computed by joining the leaving relative cache states of its predecessor blocks (b ) using the UoA join function. E.g., the predecessors of B4 are B1 and B9, such that b ∈ {B1, B9}. From the previous iteration (i = 1), the LCS r 1 B1 = {[×, 1, 0, 0]} and LCS r 1 B9 = {[×, ⊥, ⊥, 1]}. The process for computing the reaching relative cache states RCS r 2 B4 , in the next iteration i = 2, is as follows.

B1: B8) using the UoA approach.

ci BI r c0 ∓ c1 1 c2 0 c3 0 B4: ci BI r c0 ∓ c1 ∓ c2 0 c3 0 B5: ci BI r c0 ∓ c1 1 c2 ∓ c3 ∓ B6: ci BI r c0 ∓ c1 1 c2 0 c3 0 B7: ci BI r c0 ∓ c1 0 c2 1 c3 1 B8: ci BI r c0 ∓ c1 0 c2 0 c3 0 B9: ci BI r c0 ∓ c1 ∓ c2 ∓ c3 1 (a) Control flow graph Iteration Block Reaching Cache Leaving Cache (i) (b) States (RCS i b ) States (LCS i b ) 1 B1 {[×, , , ]} {[×, 1, 0, 0]} B4 {[×, ⊥, ⊥, ⊥]} {[×, ⊥, 0, 0]} B5 {[×, ⊥, ⊥, ⊥]} {[×, 1, ⊥, ⊥]} B6 {[×, ⊥, ⊥, ⊥]} {[×, 1, 0, 0]} B7 {[×, ⊥, ⊥, ⊥]} {[×, 0, 1, 1]} B8 {[×, ⊥, ⊥, ⊥]} {[×, 0, 0, 0]} B9 {[×, ⊥, ⊥, ⊥]} {[×, ⊥, ⊥, 1]} 2 B1 {[×, , , ]} {[×, 1, 0, 0]} B4 {[×, 1, 0, 0], [×, ⊥, ⊥, 1]}
Inria 1. Initialise RCS r 2 B4 = ∅ (line 29). 2. Using the UoA join function we process the LCS r of each predecessor block (B1, B9), on lines 30 to 32, one at a time (in no particular order). For illustration we will first analyse LCS r 1 B1 followed by LCS r 1 B9 as follows.

RCS r 2 B4 = J U oA (RCS r 2 B4 , LCS r 1 B1 ) = J U oA (∅, {[×, 1, 0, 0]}) = {[×, 1, 0, 0]} RCS r 2 B4 = J U oA (RCS r 2 B4 , LCS r 1 B9 ) = J U oA ({[×, 1, 0, 0]}, {[×, ⊥, ⊥, 1]}) = {[×, 1, 0, 0], [×, ⊥, ⊥, 1]}
The iterative process, repeat-until loop on lines 18 to 35, is repeated until a fixed point is reached, i.e., if two consecutive iterations have a same sets of reaching relative cache states for all blocks (line 35). For our example, it happens at the 5 th iteration, where the same set of reaching relative cache states are computed for all blocks. As a result, the reaching relative cache states of the 5 th iteration represents all the possible reaching relative cache states of the program.

Note that during the first iteration, we assumed the reaching relative cache states for blocks B4 to B9 as unknown ({[×, ⊥, ⊥, ⊥]}), but when we reach the fixed point, all the unknown cache states are resolved. Thus, we have

In summary, we have presented how to compute all possible reaching relative cache states of the reference block RCS r b ref . This corresponds to the function call on line 3 of Algorithm 6 (reproduced from Algorithm 3, which shows the overall cache analysis approach). Given the set of reaching relative cache states of the reference block (RCS r b ref ), the next step (lines 4 to 5, Algorithm 6) in our approach is to compute the number of cache misses for the worst case and the best case. The second sub problem of cache analysis (Definition 6) involves the computation of the number of cache misses for the worst case and the best case. The number of cache misses could be computed by directly analysing the relative cache state cs r = [inst r 1 , inst r 2 , . . . , inst r N -1 ]. For a cache line c i ∈ C, inst i = 1 represents a cache miss. Thus, to compute the number of cache misses for a given cs r we count the number of instances when inst i = 1. E.g., given cs r = [×, 0, 1, 1], we have two cache misses (inst r 2 = 1 and inst r 3 = 1). We define this computation in the following definition.

we remove relative cache state [×, 0, 0, 1] as it is subsumed by the cache state [×, 1, 0, 1]. Similarly, for best case analysis, J U oA +b (CS r 1 , CS r 2 ) = J U oA +b {[×, 1, 0, 1], [×, 0, 0, 1], [×, 0, 1, 0]} = {[×, 0, 0, 1], [×, 0, 1, 0]}. Here, we remove relative cache state [×, 1, 0, 1] as it is subsumed by the cache state [×, 0, 0, 1].

As illustrated in Figure 17(b), for the worst (or best) case analysis, using the function J U oA +w (or J U oA +b ) we should be able to reduce the analysis time and the memory footprint, and most importantly there should be no change in the precision compared to the non optimised approach (Figure 17(a)). For example, if we analyse the set CS r 3 = J U oA (CS r 1 , CS r 2 ) = {[×, 1, 0, 1], [×, 0, 0, 1], [×, 0, 1, 0]} for the worst case we get two misses (using wmc U oA (CS r

3 ) = 2, Definition 21) and for the best case we get one miss (using bmc U oA (CS r

3 ) = 1, Definition 22). This precision (worst/best miss count) is the same as J U oA +w ([×, 1, 0, 1], [×, 0, 1, 0]) = 2 and J U oA +b ([×, 0, 0, 1], [×, 0, 1, 0]) = 1. Thus we illustrate the precision is the same for both approaches (Figure 17(a) and Figure 17(b)).

In summary, using the fixed point computation (Algorithm 5) we have computed the reaching relative cache states of the reference block. During the fixed point computation, the optimisations presented in Section 6.7 reduces the analysis time, while not effecting the precision. Finally, as described in Section 6.6, we compute the number of cache misses for the worst case and the best case. In Table 10, we present a summary of the symbols and the definitions that were used in this section.

M AP U oA (cs r , b ref ) = M AP U oA ([×, 1, 0, 0], B8) = set 0 × set 1 × set 2 × set 3 = { , m1, m5} × { , m2} × {m3} × {m4} = {[ , , m3, m4], [ , m2, m3, m4], [m1, , m3, m4], [m1, m2, m3, m4], [m5, , m3, m4], [m5, m2, m3, m4]}
The mapping function, as defined in Definition 26, translates a relative cache state cs r into a set of concrete cache state CS. However, a block my have more than one reaching relative cache states CS r . In this case, the mapping of the cache states is an union of the possible mapping for each reaching relative cache state, i.e., given CS r = {cs r 1 , cs r 2 }, then mapping to the cache sates is

M AP U oA (cs r 1 , b ref ) ∪ M AP U oA (cs r 2 , b ref ).
We define this mapping using the following function.

Definition 27 (Extended UoA mapping function). The mapping function M AP U oA : 2 CS r × B r → 2 CS where for a given b ∈ B r and a set of relative cache states CS r ∈ 2 CS r . Then, for all relative cache states cs r i ∈ CS r where i ∈ , m6, m3, m4], and after the fixed point RCS

[1, |CS r |], M AP U oA (CS r , b) = |CS r | i=1 {M AP U oA (cs r i , b ref )} Illustration For example, given the reference block b ref is B8 with BI(b ref ) = [∓
r b ref = {cs r 1 , cs r 2 } where cs r 1 = [×, 1, 0, 0], cs r 2 = [×, 0, 1, 1] then, M AP U oA (RCS r b ref , b ref ) = M AP U oA (cs r 1 , b ref ) ∪ M AP U oA (cs r 2 , b ref ).
We start by illustrating the mapping of individual relative cache states (cs r 1 , cs r 2 ), and later present the mapping for the set of relative cache states (RCS r b ref ).

M AP U oA (cs r 1 , b ref ) = M AP U oA ([×, 1, 0, 0], B8) = { , m1, m5} × { , m2} × {m3} × {m4} = {[ , , m3, m4], [ , m2, m3, m4], [m1, , m3, m4], [m1, m2, m3, m4], [m5, , m3, m4], [m5, m2, m3, m4]} M AP U oA (cs r 2 , b ref ) = M AP U oA ([×, 0, 1, 1], B8) = { , m1, m5} × {m6} × { , m7} × { , m8} = {[ , m6, , ], [ , m6, , m8], [ , m6, m7, ], [ , m6, m7, m8], [m1, m6, , ], [m1, m6, , m8], [m1, m6, m7, ], [m1, m6, m7, m8], [m5, m6, , ], [m5, m6, , m8], [m5, m6, m7, ], [m5, m6, m7, m8]} M AP U oA (RCS r b ref , b ref ) = M AP U oA (cs r 1 , b ref ) ∪ M AP U oA (cs r 2 , b ref ) = {[ , , m3, m4], [ , m2, m3, m4], [m1, , m3, m4], [m1, m2, m3, m4], [m5, , m3, m4], [m5, m2, m3, m4]} ∪ {[ , m6, , ], [ , m6, , m8], [ , m6, m7, ], [ , m6, m7, m8], [m1, m6, , ], [m1, m6, , m8], [m1, m6, m7, ], [m1, m6, m7, m8], [m5, m6, , ], [m5, m6, , m8], [m5, m6, m7, ], [m5, m6, m7, m8]} = {[ , , m3, m4], [ , m2, m3, m4], [m1, , m3, m4], [m1, m2, m3, m4], [m5, , m3, m4], [m5, m2, m3, m4], [ , m6, , ], [ , m6, , m8], [ , m6, m7, ], [ , m6, m7, m8], [m1, m6, , ], [m1, m6, , m8] [m1, m6, m7, ], [m1, m6, m7, m8], [m5, m6, , ], [m5, m6, , m8] [m5, m6, m7, ], [m5, m6, m7, m8]}
Finally, we have presented the mapping function M AP U oA (Definition 27), which computes the corresponding concrete cache states from a given set of relative cache states. Next, we present a detailed comparison between the NUS, Absint and the proposed approaches.

Inria

Comparison between the approaches

In this section, we start by presenting a summary of the three approaches that were presented in this chapter.The NUS approach (see Section 3) and the Absint approach (see Section 4) solve the cache analysis problem (Definition 6) by analysing all basic blocks in a single fixed point computation. In contrast, the proposed (UoA) approach (see Section 6) analyses one basic block at a time. Given a cache model CM , using Figure 18, we discuss how the three approaches analyse a basic block (b). Before we discuss the approaches, we present the meaning of the different components of the figure .  A domain is represented as an ellipse. For example, the figure has four domains: (1) Domain 1 that represents all possible relative cache states, ( 2 ), the precision is same as the NUS approach. Thus, the precision is also represented by the point P N U S (b), in Domain 4.

We now compare the three approaches by first comparing the computed concrete cache states (Domain 3) and then the precision (Domain 4). We illustrate this idea using the example cache model (Figure 2). For the basic block B8, Table 12 presents comparison of the three approaches. For the NUS approach (row 1), the concrete reaching cache states of B8 are presented in column 3. For the Absint approach (row 2), the abstract reaching cache state of B8 and the corresponding concrete cache states are presented in columns 2 and 3 respectively. It contains 8 possible concrete cache states. Similarly, for the UoA approach, the reaching relative cache states and the corresponding Inria concrete cache states are presented in columns 2 and 3 respectively. It contains 18 possible concrete cache states.

As stated earlier, we observe that the set of concrete cache states corresponding to the NUS approach (only 2 cache states) is a subset of the concrete cache states corresponding to the Absint (8 cache states) and the UoA (18 cache states) approaches. This shows that the NUS approach yields the smallest set of possible reaching cache states.

Comparing the precision: In Domain 4, we presented the precision of the NUS, Absint and UoA approaches. We illustrate that always the precision computed by the UoA approach is the same as the NUS approach and, the precision from the Absint approach is always less than or equal to the NUS/UoA approaches (P N U S (b) ≤ P Abs (b)). We illustrate this idea using Table 12. For the block B8 (BI(B8) = [∓, m6, m3, m4]), given the set of possible reaching concrete cache states for each approach (in column 3), the precision (wmc, bmc) are presented in columns 4 and 5 respectively. As stated earlier, the precision from the NUS approach (2, 1) is the same as the UoA approach (2, 1).

Also, we observe that the precision of the Absint approach is(3, 0). For the worst case, the wmc for the Absint is greater than the NUS approach (3 > 2), making Absint approach less precise. Similarly, for the best case, the bmc for the Absint is smaller than the NUS approach (0 < 1), making Absint approach less precise. Thus, as illustrated in Domain 4, the NUS approach is more precise than the Absint approach (P N U S (B8) = (2, 1) ≤ (3, 0) = P Abs (B8)). [m5, m6, m3, m4] Absint Finally, using Table 13, we present a qualitative comparison between the three approaches.

Approach arcsB8/RCS r B8 RCSB8 wmc(B8) bmc(B8) (Worst) (Best) NUS [m5, m2, m3, m4] 2 1
(1) The NUS approach analyses all blocks using a single fixed point computation. It directly computes all possible reaching concrete cache states of all blocks, because it does not introduce any abstractions. The lack of abstraction yields high precision, but longer analysis time. [START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF] The Absint approach analyses all blocks using a single fixed point computation. However, the notion of abstract cache states is introduced which abstracts the relation between cache lines. This allows for faster analysis time, but sacrifices precision. (3) Finally, the UoA approach analyses one block at a time. It introduces the notion of relative cache states. This abstraction does not sacrifice the precision (same as NUS). Later in Section 9, using experimental results, we quantitatively compare the three approaches in terms of precision and analysis time.

Discussion

We started by formalising the cache model CM (presented in Definition 1). The model contains the instructions (I) and the set of cache lines (C), where each instruction is mapped to a single cache line. We assume that whenever there is a cache miss, only one instruction is fetched from the main memory. However, in practice, this assumption is not true. Whenever there is a cache miss, a set of instructions, called memory block, are fetched from the main memory and stored in a cache line. This execution model is identical to the analytical model presented by the NUS approach [START_REF] Negi | Accurate Estimation of Cache-Related Preemption Delay[END_REF]. In order to map the execution model to the cache model presented in this chapter, we treated each memory block as an instruction. Then, each cache line stored one memory block instead of one instruction.

To fairly compare the three approaches, we presented the Absint approach in a slightly different manner to match the NUS and the UoA approaches. However, the differences do not affect the core technique of the Absint approach [START_REF] Ferdinand | Cache Behavior Prediction by Abstract Interpretation[END_REF]. The Absint approach as described in [START_REF] Ferdinand | Cache Behavior Prediction by Abstract Interpretation[END_REF], presents two different analyses. The May/Must analysis computes the instructions that may/must be in the reaching cache state of a basic block. This analysis is used to compute the number of cache misses in the best/worst case. However, given the results of the May analysis, both the worst case and the best case cache misses can be derived, avoiding the need for Must analysis. Thus, in this chapter, during the fixed point computation (Algorithm 2) we only illustrated the May analysis. Also, during the initialisation of the fixed point computation in the Absint approach, an empty set is used to represent an unknown instruction. However, to maintain consistent terminology w.r.t the NUS approach, we used the symbol ⊥.

One cache analysis approach that we did not compare with is the Cache Conflict Graphs [START_REF] Li | Accurate timing analysis by modeling caches, speculation and their interaction[END_REF][START_REF] Li | Performance estimation of embedded software with instruction cache modeling[END_REF]. This approach analyses the number of cache misses in each block, one cache line at a time. For our example (Figure 2), the cache model has four cache lines c 0 , c 1 , c 2 and c 3 . We would generate four graphs, one for each cache line c i , where each graph captures the instructions that are mapped to the cache line c i . Then, by traversing each graph and looking at the predecessor basic block, the cache hit (or miss) of each basic block can be computed for the particular cache line. A cache hit occurs when the instruction appears in the predecessor block, otherwise, it is a Inria cache miss. We believe, by analysing one cache line at a time, the relation between cache lines is abstracted away. This abstraction is similar to the join function (Definition 11) of the Absint approach. Thus, we would expect the precision of the Cache Conflict Graphs to be identical to the precision of the Absint approach. However, it would be interesting to compare the analysis time.

Benchmarking and Experimental Results

In this section, we compare the precision and computation time between the NUS, the Absint, and the UoA approaches. Here, we compare the WCRT, BCRT, and the analysis time over a set of benchmarks.

For the experiments, we have selected five examples from [START_REF] Kuo | Determining the worst-case reaction time of IEC 61499 function blocks[END_REF] that model control applications. These examples are developed using the model-driven engineering approach defined by the IEC 61499 international standard for describing industrial process-control systems [?]. It prescribes the use of function blocks to facilitate a component-oriented approach to software development for industrial process-control systems. Each example contains a collection of function blocks and, all blocks are executed in a round-robin fashion to emulate the semantics of scan cycles of programmable logic controllers (PLC). The program runs periodically in a sequence of scan cycles. This is similar to the execution of PRET-C program that runs periodically in a sequence of ticks. Using an automated tool, similar to the work presented in [START_REF] Kuo | Determining the worst-case reaction time of IEC 61499 function blocks[END_REF], we translate each function block into a PRET-C thread. EOT statements are then used to mark the computation boundaries for each scan cycle.

All five examples are presented in last five rows in Table 14. The first column presents the example followed by its description (column 2). The number of PRET-C lines of the program and its memory footprint is presented in columns 3 and 4 respectively. The largest example are CruiseController and RailRoadCrossing with more than 4000 lines of PRET-C code. We have also created two additional examples: a BubbleSort program and a Synthetic example. The latter example is introduced to highlight the difference between the NUS, Absint and UoA approaches.

Example

Benchmarking

In our experiment, we compare WCRT, BCRT and analysis time of Absint, the UoA, and the NUS approaches. The results are presented in Table 15. For this experiment, we have configured the cache size to be 1% of the program size. We have chosen this cache size because, in practice, the size of the cache is significantly smaller that the program size. For example, the MicorBlaze processor has a main memory of size 128 MB and, the cache size can be configured from anything between 128 bytes to 128 KB (0.001% to 1% of the mian memory) [START_REF]MicroBlaze Processor Reference Guide[END_REF]. The WCRT, BCRT, and the analysis time (in seconds) for Absint is presented in columns 2, 3, and 4 respectively. Similarly, the following columns present results for the UoA and NUS approaches. For most examples, the NUS approach takes longer than 12 hours. In this case, we were not able to calculate the WCRT and the BCRT values. This was represented using "T.O" (Time Out). Finally, the last column of the table presents the gain in precision on the WCRT estimate of the UoA approach, compared to the Absint approach.

For WCRT analysis, across all the benchmarks, we observe that the estimates from the UoA approach is always less than or equal to the estimates from the Absint approach. Also, the estimates from the UoA approach are always equal to the estimates from the NUS approach. This shows that the UoA approach does not lose any precision.

For BCRT analysis, across all the benchmarks, we observe that the estimates from the UoA approach is always greater than or equal to the estimates from the Absint approach. Also, the estimates from the UoA approach are always equal to the estimates from the NUS approach. This shows that the UoA approach does not lose any precision.

The abstractions presented for UoA approach also significantly reduces the analysis time, when compared to the NUS approach (see earlier comparison in Section 7). For most of the examples, the NUS approach does not finish (more than 12 hours) its computation, while the UoA approach takes less than 3 minutes. However, the UoA approach is slightly longer than the Absint approach.

For the biggest example (RailRoadCrossing), the UoA approach is 24% (1.24 in the last column) tighter then the Absint approach. More importantly, this experiment shows that, on an average, the UoA approach is more precise (less abstract) than the Absint approach. At the same time, it is always as precise (i.e., no loss in precision) as the NUS approach, while being significantly faster than the NUS approach, and marginally longer than the Absint approach. This idea is illustrated using Figure 19. Overall, this is a significant result that supports the contribution (UoA approach as a new cache analysis technique) of this chapter. In this paper, we have formally described the cache analysis model and presented three approaches for solving it. First, the NUS approach, which does not introduce any abstractions resulting in a very precise, but very slow analysis. In contrast, the Absint approach abstracts the relation between the cache lines. This allows for faster analysis time, but sacrifices precision. Finally, we have presented a new approach, called UoA approach, which abstracts the instructions and cache states w.r.t. to a reference block. This does not sacrifice any precision. Experimental results reveal that the precision of the UoA approach is the same as the NUS approach, but more precise than the Absint approach. Also, the analysis time is much shorter than the NUS approach, but longer (on average by 1 minute) than the Absint approach. Illustration of functions J U oA +w and J U oA

Figure 1 :

 1 Figure 1: Memory hierarchy

Figure 2 :

 2 Figure 2: (a) A simple control flow graph consisting of nine basic blocks (B1 to B9) and the instructions that are accessed during execution of the basic block. (b) Mapping of instructions on to four cache lines (c 0 to c 3 ).

  Inriaexecution of a basic block and the Leaving cache states (LCS) represent the set of cache states after the execution of the basic block. We denote the RCS of a basic block b as RCS b and the LCS of a basic block b as LCS b .

  e., BI(b)[i] = ∓) and further the instruction does not match with the instruction in the reaching cache state (i.e., BI(b)[i] = cs[i]). Using Definition 20, we define a function that computes the number of cache misses. Definition 3 (Miss count). The cache miss function, mc : B × CS × C → {0, 1}, where for any block b ∈ B, cache state cs and a cache line

Figure 4 :

 4 Figure 4: Illustration of the function mc

Definition 4 (

 4 Worst miss count). We define the function wmc : B×2 CS → N 0 where, for a given block b ∈ B and a set RCS ⊆ CS such that RCS = {rcs 1 , rcs 2 , . . . , rcs m } and m = |RCS |, wmc(b, RCS ) = M AX(mc(b, rcs 1 ), . . . , mc(b, rcs m )) Definition 5 (Best miss count). We define the function bmc : B × 2 CS → N 0 where, for a given block b ∈ B and a set RCS ⊆ CS such that RCS = {rcs 1 , rcs 2 , . . . , rcs m }, bmc(b, RCS ) = M IN (mc(b, rcs 1 ), . . . , mc(b, rcs m ))

2 .

 2 P : B → N 0 × N 0 , where for every block b ∈ B, P (b) = (wmc(b, RCS b ), bmc(b, RCS b )) for all b ∈ B. We refer to this second problem as sub problem two.

3

 3

Definition 8 (

 8 NUS transfer function). The NUS transfer function is T N U S : B × CS → CS where, for a given basic block b ∈ B and a cache state cs, T N U S (b, cs) = cs where for all cache lines

Figure 5

 5 Figure 5 illustrates the operation of the transfer function T N U S . Given block b, with BI(b) = [m5, ∓, ∓, ∓], and a reaching cache state cs = [m1, m2, m3, m4], the leaving cache state cs = T N U S (b, cs) is computed as follows.

Inria

Figure 5 :

 5 Figure 5: Illustration of the NUS transfer function

Definition 9 (

 9 Extended NUS transfer function). The NUS transfer function is T N U S : B × 2 CS → 2 CS where, for a given basic block b ∈ B and a set of cache states CS ⊆ 2 CS , T N U S (b, CS) = CS where for all cache states cs i ∈ CS where i ∈ [1, |CS|], CS = |CS| i=1 {T N U S (b, cs i )} In Figure 3, block B8 has two reaching cache states (RCS B8 = {cs 1 , cs 2 }) where cs 1 =

  Input: A cache model CM = I, C, CI, G, BI Output: RCS b for every block b ∈ B. 1: i = 1 {iteration counter} 2: {Initialise the RCS of all blocks} 3: for each b ∈ B do 4:

  c) Reaching and leaving cache states

Figure 6 :

 6 Figure 6: Computing all possible reaching cache states using the NUS approach.

  of a basic block b as arcs b and the abstract leaving cache state of a basic block b as alcs b . Illustration of abstract cache states Using Figure 7, we illustrate abstract reaching/leaving cache states of a block. Initially the cache is empty. The state of the cache is acs = [{ }, { }, { }, { }]. After the execution of block B1, cache lines c 0 , c 1 , c 2 , c 3 will contain instructions m1, m2, m3, m4 respectively, resulting in the acs = [{m1}, {m2}, {m3}, {m4}]. The abstract cache state [{ }, { }, { }, { }] is the abstract state of the cache prior to the execution of the basic block B1. Thus, arcs B1 = {[{ }, { }, { }, { }]} is the abstract reaching cache state of block B1. Similarly, alcs B1 =[{m1}, {m2}, {m3}, {m4}] is the abstract leaving cache state of block B1.

Figure 7 :

 7 Figure 7: Illustration of the abstract cache states.

Definition 12 (

 12 Absint transfer function). The Absint transfer function is T Absint : B × ACS → ACS where, for a given basic block b ∈ B and an abstract cache states acs ∈ ACS, T Absint (b, acs) = acs where for all cache lines c i ∈ C where i ∈ [0, N -1] then,

Figure 8 :

 8 Figure 8: Illustration of the Absint transfer function

Inria Algorithm 2

 2 Fixed-point computation for the Absint approachInput: A cache model CM = I, C, CI, G, BI Output: arcs b for every block b ∈ B. 1: i = 1 {iteration counter} 2: {Initialise the arcs of all blocks} 3: for each b ∈ B do {Compute the set of leaving cache states for all blocks for iteration i} 12:

  , ∅, . . . , ∅] {Empty vector} 22: for each alcs i b , where (b , b) ∈ E do until ∀b ∈ B, arcs i b = arcs i-1 b {Termination condition} 28: return arcs i b for all b ∈ B 4.4.1 Illustration of the fixed-point algorithm

Figure 9 :

 9 Figure 9: Computing all possible abstract reaching cache states using the Absint approach.

  : A cache miss can occur on cache line c i , if b has an instruction (BI(b)[i] = ∓), and BI(b)[i] is not the only instruction contained in the abstract reaching cache state on cache line c i ({BI(b)[i]} = arcs[i]). For the above example, the block B8 executes the instruction m6 on cache line c1, whereas the cache may contain either m2 or m6. Hence, for a cache line c 1 , in the worst case, we have a cache miss ({BI(B8)[START_REF]MicroBlaze Processor Reference Guide[END_REF]} = {m6} = {m2, m6} = arcs[START_REF]MicroBlaze Processor Reference Guide[END_REF]).Best case analysis: A cache miss can occur on cache line c i , if b has an instruction (BI(b)[i] = ∓), and BI(b)[i] is not present in the abstract reaching cache state on cache line c i (BI(b)[i] ∈ arcs[i]). For the above example, the block B8 executes the instruction m4 on cache line c8, whereas the cache contains only m8. Hence, for a cache line c 3 , in the best case, we have a cache miss (BI(B8)[START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = m4 ∈ {m8} = arcs[START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]).

Definition 14 ( 1 :

 141 Absint worst miss count). We define the Absint worst miss count function wmc Absint : B × ACS → N 0 where, for a given block b ∈ B, an abstract cache state acs ∈ ACS is, wmc Absint (b, acs) = if BI(b)[i] = ∓ and {BI(b)[i]} = acs[i] 0 : otherwise Definition 15 (Absint best miss count). We define the Absint best miss count function bmc Absint : B × ACS → N 0 where, for a given block b ∈ B and an abstract cache state acs ∈ ACS is, bmc Absint (b, acs) =

Figure 10 :

 10 Figure 10: Illustration of the functions wmc Absint and bmc Absint ure 10 we now illustrate the functions wmc Absint and bmc Absint .During a worst case analysis, for cache line c 0 , we do not have a cache miss, wmiss 0 = 0, because the block B8 does not have any instruction mapped to c 0 (BI(B8)[0] = ∓). For cache line c 1 , we have a cache miss, wmiss 1 = 1, because the block needs to execute m6 and it is not the only possible instruction in the cache ({BI(B8)[START_REF]MicroBlaze Processor Reference Guide[END_REF]} = {m6} = {m2, m6} = acs[START_REF]MicroBlaze Processor Reference Guide[END_REF]). Similarly, wmiss 2 = 0, because m3 is not the only possible instruction in the cache ({BI(B8)[START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]} = {m3} = {m3, m7} = acs[START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]). Finally, for the cache line c 3 , we have a cache miss, wmiss 3 = 1, because the block needs to execute m4, while the cache contains m8 ({BI(B8)[START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]} = {m4} = {m8} = acs[START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]). Thus, for the four cache lines, in the worst case, we get three misses (wmc Absint (B8, acs) = 0 + 1 + 1 + 1 = 3).During a best case analysis, for cache line c 0 , we do not have a cache miss, bmiss 0 = 0, because the block B8 does not have any instruction mapped to c 0 (BI(B8)[0] = ∓). For cache line c 1 , we have a possible cache hit, wmiss 1 = 1, because the block needs to execute m6 and it is present in the set of possible instruction in the cache ({BI(B8)[START_REF]MicroBlaze Processor Reference Guide[END_REF]} = {m6} ∈ {m2, m6} = acs[START_REF]MicroBlaze Processor Reference Guide[END_REF]). Similarly, for the cache line c 1 , we have a possible cache hit wmiss 2 = 1, because m3 is present in the set of possible instruction in the cache ({BI(B8)[START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]} = {m3} ∈ {m3, m7} = acs[START_REF] Byhlin | Applying static WCET analysis to Automotive Communication Software[END_REF]). Finally, for the cache line c 3 , we have a cache miss, wmiss 3 = 1, because the block needs to execute m4 and the instruction is not in the cache ({BI(B8)[START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]} = {m4} ∈ {m8} = acs[START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF]). Thus, for the four cache lines, in the best case, we get three misses (bmc Absint (B8, acs) = 0 + 0 + 0 + 1 = 1).

Figure 11 :

 11 Figure 11: NUS and Absint approaches on precision vs analysis time.

Observation 1 :

 1 A reference block b ref may not refer to all the cache lines during its execution. The unrefereed cache lines, can be ignored during the analysis of b ref . Further, we can remove vacuous blocks from the graph, if all their instruction(s) are mapped to the unrefereed cache lines (w.r.t b ref ). For example, given BI(B8) = [∓, m6, m3, m4], BI(B1) = [m1, m2, m3, m4] and BI(B2) = [m5, ∓, ∓, ∓], during the analysis of block B8 (b ref = B8), we observe that B8 does not execute any instruction on the cache line c 0 (BI(B8

Observation 2 :

 2 For a cache line c i , a reference block b ref can experience a cache hit (or miss) only when the instruction executed by b ref is the same (or different) as the instruction in the reaching cache state. During the analysis of block b ref , all instructions that can be executed on cache line c i (for every block b in the CFG) can be abstracted as same (0) when BI(b)[i] = BI(b ref )[i], or different (1) when BI(b)[i] = BI(b ref )[i], or as no instruction (∓) when there is no instruction on c i in b (BI(b)[i] = ∓), or as not of interest (×) when there is no instruction on c i in b ref (BI(b ref )[i] = ∓).

4 : 5 :

 45 Input: A cache model CM = I, C, CI, G, BI . Output: Compute the worst/best miss count (wmc/bmc) for all basic blocks in B. 1: for each b ref ∈ B do 2: (G r , B r ) = Reduce(CM, b ref ) {Reduced graph and relative instructions (Section 6.2)} 3: RCS r b ref = F PUoA(CM, G r , BI r ) {Compute reaching relative cache states (Section 6.5)} wmc = wmcUoA(RCS r b ref ) {Cache miss in the worst case (Section 6.6)} bmc = bmcUoA(RCS r b ref ) {Cache miss in the best case (Section 6.6)} 6: P (b ref ) = (wmc, bmc) {Solution for the second sub problem (Definition 6)} 7: end for 8: return P (b) (wmc, bmc) for all basic blocks b in B

2 :

 2 Relative instruction mapping (lines 7 to 22) Based on Observation 2, given a reference block b ref ∈ B and a cache line c i , the instruction of any blocks b 1 ∈ B r can be expressed as different (1) when BI(b 1 )[i] = BI(b ref )[i] (checked on line 12), or same (0) when BI(b 1 )[i] = BI(b ref )[i] (checked on line 15), or no instruction (∓) when there is no instruction in b 1 on cache line c i , BI(b 1 )[i] = ∓ (checked on line 18), or not of RR n°8214 interest (×) when there is no instruction in b ref on cache line c i , BI(b ref )[i] = ∓ (checked on line 9). This relation is captured using the relative instruction mapping BI r (b 1 ). For example, given BI(b ref ) = [∓, m6, m3, m4] and BI(b1) = [m1, m2, m3, m4], we illustrate the relative instruction mapping function BI r using Figure 13, • For cache line c 0 , BI r (b 1 )[0] = × because, the reference block b ref does not have an instruction (BI(b ref )[0] = ∓). • For cache line c 1 , BI r (b 1 )[1] = 1 because, the reference block b ref has an instruction m6 which is different to the instruction m2 of the basic block b 1 (BI(b ref )[1] = m6 = m2 = BI(b 1 )[1]). • For cache line c 2 , BI r (b 1 )[2] = 0 because, the reference block b ref has the instruction m3 which is the same as the instruction in the basic block b 1 (BI(b ref )[2] = m3 = BI(b 1 )[2]). • For cache line c 3 , BI r (b 1 )[3] = ∓ because, the basic block b 1 does not have an instruction (BI(b 1 )[3] = ∓).

Step 3 :

 3 (a), the relative mapping (w.r.t B8) for every block is shown in Figure 12(b). Note that for all blocks b in B r , if the reference block (b ref ) does not have an instruction on cache line c i (BI(b ref )[i] = ∓), then for cache line c i , the relative instruction for all blocks is × (BI r (b)[i] = ×). This shows that during the analysis of b ref , the cache line c i is not considered. For example, in Figure 12(b), the reference block B8 does not have an instruction on cache line c 0 (BI(B8)[0] = ∓). Thus, for cache line c 0 , the relative instruction for all blocks is × (BI r (b)[i] = ×). Remove vacuous blocks and update edges (lines 24 to 44) Based on Observation 1, we can remove vacuous blocks which do not affect the precision of the reference block b ref . We define a block b 1 ∈ B r to be vacuous, if BI r (b 1 ) ∈ ({×, ∓}) N .

  (b), blocks B2 and B3 do not contain any relative instructions (BI r (B2) = [×, ∓, ∓, ∓] and BI r (B3) == [×, ∓, ∓, ∓], thus, they are removed for the graph and the updated graph G r is presented in Figure 12(c). This is the reduced graph G r (w.r.t to b ref = B8). So far, we have presented how to reduce the graph size (Reduce(CM, b ref ) = (G r , BI r )), and compute the relative instruction mapping function BI r . Due to the relative instructions, cache states also needs to be represented using relative instructions. The next step describes the behaviour of the cache. Inria Algorithm 4 Reduce: Reduce the CFG and abstract instructions.

Input:

  Cache model CM = I, C, CI, G, BI and a reference block b ref ∈ B. Output: G r = B r , b init , E r and BI r : B r → ({×, ∓, 1, 0}) N 1: {Step 1: Initialise} 2: B r = B, E r = E, G r = B r , b init , E r {Copy all blocks and edges} 3: for each b 1 ∈ B r do 4: BI r (b 1 ) = ∅ {Initialise the vector BI r (b 1 )} 5: end for 6: {Step 2: Relative instruction mapping} 7: for each b 1 ∈ B r do 8:

23: {Step 3 :

 3 Remove vacuous blocks and update edges} 24: for each b 1 ∈ B r do 25: if (BI(b 1 ) ∈ ({×, ∓}) N ) ∧ (b 1 = b init ) {check for all vacuous blocks, excluding initial block} then 26: {Compute predecessors and successors of b 1 } 27:

Figure 12 :

 12 Figure 12: Illustration of Algorithm 4 with b ref = B8.

Inria

  c

Figure 13 :

 13 Figure 13: Illustration of the function BI r (b)

  r.t the instruction (BI(b ref )[i]) in the block b ref . For a cache line c i ∈ C: • inst r i = 1 represents that the instruction in the cache is different to the instruction executed in the reference block b ref . E.g., BI(b ref )[i] = m1 and inst r i = 1 represents that the instruction on the cache is not m1. • inst r i = 0 represents that the instruction in the cache is same as the instruction executed in the reference block b ref . E.g., BI(b ref )[i] = m1 and inst r i = 0 represents that the instruction on the cache is m1.

Figure 14 :

 14 Figure 14: Illustration of the relative cache states.

Figure 15 :

 15 Figure 15: Illustration of the UoA transfer function

Algorithm 5 F 2 :

 52 P U oA : Fixed point computation for UoA approach Input: A cache model CM = I, C, CI, G, BI , reduced graph G r = B r , binit, E r and BI r : B r → ({×, ∓, 1, 0}) N . Output: Reaching relative cache states of block b ref (RCS r b ref ). 1: {Initialise cs r and cs r ⊥ } for each ci ∈ C do 3:

  {When b ref has no instruction (in this case, BI r (b ref ) = ×) on cache line ci, initialise empty/unknown cache states as not of interest.} cs r [i] = , cs r ⊥ [i] = ⊥ {When b ref has an instruction on cache line ci, initialise empty/unknown cache states as /⊥.} 7: end if 8: end for 9: i = 1 {iteration counter} 10: {Initialise RCS r for all blocks } 11: for each b ∈ B do 12: if b = binit then 13: RCS r 1 b init = {cs r } {for the initial block, the initial state of the cache is always empty} r ⊥ } {for rest of the blocks, the initial state of the cache is unknown} until ∀b ∈ B r , RCS r i b = RCS r i-1 b {Termination condition} 36: return RCS r b ref

Figure 16 :

 16 Figure 16: Computing all possible reaching relative cache states of the reference block b ref (B8) using the UoA approach.

Algorithm 6

 6 Overview of the proposed approach (reproduced from Algorithm 3) Input: A cache model CM = I, C, CI, G, BI . Output: Compute the worst/best miss count (wmc/bmc) for all basic blocks in B. 1: for each b ref ∈ B do 2: (G r , B r ) = Reduce(CM, b ref ) {Reduced graph and relative instructions (Section 6.2)} 3: RCS r b ref = F PUoA(CM, G r , BI r ) {Compute reaching relative cache states (Section 6.5)} 4: wmc = wmc(b ref , RCS b ref ) {Cache miss in the worst case (Section 6.6)} 5: bmc = bmc(b ref , RCS b ref ) {Cache miss in the best case (Section 6.6)} 6: P (b ref ) = (wmc, bmc) {Solution for the second sub problem (Definition 6)} 7: end for 8: return P (b) (wmc, bmc) for all basic blocks b in B 6.6 Calculating cache misses for the reference block

  acs =[{ , m1, m5}, { , m2}, {m3}, { , m8}]. Then using the abstract cache state to cache state mapping function (described in Definition 13), we get the set of cache states cs as,{[ , ,m3, m4], [ , m2, m3, m4], [m1, , m3, m4], [m1, m2, m3, m4], [m5, , m3, m4], [m5, m2, m3, m4]} This translation is described by the following function. Definition 26 (Relative cache state to cache state mapping). Given a cache model CM , the UoA mapping function is M AP U oA : CS r × B r → 2 CS , where for a given relative cache state cs r ∈ CS r and b ∈ B r . M AP U oA (cs r , b) = set 0 × set 1 × . . . × set N -1 where, set i = M AP inst U oA (c i , cs r [i], b). Illustration For example, given cs r = [×, 1, 0, 0], and the reference block b ref is B8 with BI(b ref ) = [∓, m6, m3, m4] then,

Figure 18 :

 18 Figure 18: Overview of NUS, Absint and UoA approaches for computing the worst/best cache misses for a block b

=

  Comparing the concrete cache states: In Domain 3, we illustrate that: (1) the concrete cache states corresponding to the NUS approach (RCS N U S b) is always a subset (or equal) of the concrete cache states corresponding to the Absint and the UoA approaches (RCS N the concrete cache states corresponding to the Absint and the UoA approaches may not be equal (RCS Absint b

Figure 19 :

 19 Figure 19: Comparing WCET and analysis time for the last five examples (1% relative cache size)

  +b . . . . . . . . . . . . . . . . . . . . . 10 Some of the symbols and the definitions presented in this section. . . . . . . . . . 11 Illustration of the function M AP inst U oA w.r.t cache line c 0 , BI(b ref )[0] = m1 and CI(c 0 ) = {m1, m5} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Comparing the cache states and the precision between the NUS, the Absint and the UoA approaches as we analyse block B8 (BI(B8) = [∓, m6, m3, m4]). . . . . 13 Qualitative comparing the precision between the NUS, the Absint and the UoA approaches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Benchmark programs and their characteristics. . . . . . . . . . . . . . . . . . . . 15 Quantitative comparison between Absint, UoA, and NUS approaches . . . . . . . Inria RESEARCH CENTRE GRENOBLE -RHÔNE-ALPES Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Table 1 :

 1 Some of the symbols and the definitions (Illustrated usingFigures 3)

	/Definition Description	Example
	CM	Cache model of a given	see Section 2.1
		program
	B	Set of basic blocks	{B1, B2, . . . , B9} in Figure 2
	I	Set of instruction	{m1, m2, . . . , m8} in Figure 2
	C	Ordered set of cache	{c 0 , c 1 , c 2 , c 3 } in Figure 2
		lines
	CI : C → 2 I	Maps cache line to a set	CI(c 0 ) = {m1, m5}
		of instructions
	IC : I → C	Maps instruction to a	IC(m1) = c 0
		cache line
	BI : B → (I ∪ {∓}) N Maps instructions exe-	BI(B1) = [m1, m2, m3, m4] then
		cuted by the block to	BI(B1)[0] = m1
		cache lines
	BI(b)[i] = ∓	Block b has no instruc-	BI(B1) = [∓, m2, m3, m4] then
		tion on cache line c i	BI(B1)[0] = ∓
	cs	Cache state	cs = [m1, m2, m3, m4] and cs[0] =
			m1
	cs[i] =	Cache state has no in-	cs[0] =
		struction on cache line c i
	cs[i] = ⊥	Cache state has an un-	cs[0] = ⊥
		known instruction on
		cache line c i
	cs	Empty cache state	cs = [ , , , ]
	cs ⊥	Unknown cache state	cs = [⊥, ⊥, ⊥, ⊥]
	RCS b	Set of reaching cache	RCS B8	=	{[m5, m2, m3, m4],
		states of block b	[m5, m6, m7, m8]}
	LCS b	Set of leaving cache	LCS B8 = {[m5, m6, m3, m4]}
		states of block b
	N 0	Natural numbers that	N 0 = {0, 1, 2, 3, . . .}
		includes zero
	mc : B × CS → N 0	Computes the number	BI(B8) = [∓, m6, m3, m4] and cs =
		of cache misses experi-	[m5, m2, m3, m4] then mc(B8, cs) =
		enced by the block for a	1
		given cache state
	wmc : B × 2 CS → N 0 Computes the maxi-	wmc(B8, RCS B8 ) = 2
		mum number of cache
		misses
	bmc : B × 2 CS → N 0	Computes the minimum	bmc(B8, RCS B8 ) = 1
		number of cache misses
					Inria

  1 B9 = [{⊥}, {⊥}, {⊥}, {m8}]. The process for computing arcs 2 B2 is as follows. 1. Initialise arcs 2 B2 = [∅, ∅, . . . , ∅] (line 21). 2.

Table 13 :

 13 Qualitative comparing the precision between the NUS, the Absint and the UoA approaches.

Table 14 :

 14 Benchmark programs and their characteristics.

		Description	Number of	Size
			PRET-C lines	(source file)
	BubbleSort	Bubble sort program.	128	2KB
	Synthetic	Contains branching and loops 180	4KB
	Flasher	Control for distributed lights	384	9KB
	DrillStation	Controlling a drilling station	1800	62KB
	ConvBelt	Airport baggage conveyor belt 1280	44KB
	RailRoadCrossing Rail road intersection cnt.	4613	163KB
	CruiseController	Cruise control model	4194	146KB

Table 15 :

 15 Quantitative comparison between Absint, UoA, and NUS approaches

	10 Conclusions

RR n°8214

Inria

This project is partially funded by the SPADES project

(cs r

1 [i] = ⊥). In this case, we can remove cs r 1 , as it does not contain any extra information compared to cs r 2 . For example, let RCS r 3 = LCS r 1 ∪ LCS r 2 which contains two relative cache states cs r 1 = [1, ⊥, ⊥, ⊥] and cs r 2 = [1, ⊥, 0, ⊥]. Since cs r 1 is subsumed by cs r 2 , we can reduce the reaching relative cache states of b to RCS b = {[1, ⊥, 0, ⊥]}. This idea of subsumed relative cache states is further explained during the fixed point computation.

Intuitively, when joining two sets of reaching relative cache states, the join function retains only those relative cache states that can not be subsumed. The join function for our approach is defined in Definition 17.

Definition 17 (UoA join function). The UoA join function J U oA : 2 CS r × 2 CS r → 2 CS r where for any two sets of relative cache states CS r 1 ∈ 2 CS r and CS r 2 ∈ 2 CS r ,

where, S U oA : CS r × CS r → {true, f alse} where, for any cs r 1 , cs r 2 ∈ CS r , Using Table 6, we first illustrate the UoA subsumed function (S U oA ). In the first row, given two relative cache states cs r 1 = [×, 1, ⊥, ⊥] and cs r 2 = [×, 1, ⊥, 0], S U oA (cs r 1 , cs r 2 ) = true. This shows the case when cs r 1 is subsumed by cs r 2 . In the second row, given two cache states

2 ) = f alse. This shows the case when cs r 1 is not subsumed by cs r 2 . Using Table 7, we illustrate the UoA join function. Given two sets of relative cache states

UoA transfer function

The UoA transfer function describes how a reaching relative cache state cs r

RR n°8214

Definition 20 (UoA miss count). The UoA miss count function, mc U oA : CS r → N 0 , where for any relative cache state cs r ∈ CS r and a cache line c i ∈ C with i ∈ [0, N -1] is defined as follows:

where,

The mc U oA function computes the number of cache misses for a given reaching relative cache state. However, if there is more than one reaching relative cache states (CS r ), the number of cache misses can vary. For cache analysis, we are interested in finding the worst/best case number of cache misses that may be experienced by a basic block. This can be computed by calculating the maximum/minimum number of cache misses. It is defined using the following two functions.

Definition 21 (UoA worst miss count). We define the function wmc U oA : 2 CS r → N 0 where, for a set of relative cache states CS r 1 ∈ 2 CS r such that CS r 1 = {cs r 1 , cs

In summary, for a given reference block b ref ∈ B, we have computed the number of cache misses for the worst case and the best case. To complete the cache analysis, we repeat this process for each basic block in B (lines 1 to 6, Algorithm 6). In the next section, we present an optimisation that can be applied to our approach to reduce the analysis time while maintaining the precision.

Reducing the analysis time

Figure 17(a) presents our current approach (presented in the previous section). Here, given a cache model CM and a reference block b ref , using a fixed point computation (Algorithm 5) all possible reaching relative cache states of the reference block are computed (CS r b ref ). Then using the the functions wmc U oA and bmc U oA , the worst and best case cache misses are computed. CS

Table 8: Reducing cache states based on the worst/best case analysis.

In this section, we propose to customise our current approach to analyse either for the worst case or the best case. Our intuition is that by analysing only the worst case (or the best case) allows us to ignore cache states that are not relevant, i.e, during the worst case analysis, we can ignore cache states that represent the best case. Using this customisation, we may be able to reduce the number of iterations required to reach the fixed point, and may result in faster analysis time, while not effecting the precision.

For example, given

, [0, 0, 0, 0]}, during the fix-point computation if we are only analysing for worst case, we can reduce CS r to {[1, 1, 1, 1]} because it captures the worst case (four misses) relative cache state and the rest can be removed. Similarly, for the best case we can reduce CS r to {[0, 0, 0, 0]} because it captures the best case (zero misses) relative cache state and the rest can be removed. Now, consider the CS r with five possible relative cache states (CS r = {cs r 1 , cs r 2 , cs r 3 , cs r 4 }) presented in column 1 of Table 8. To decide on what cache states can be subsumed (removed) is not very trivial. The decision on how to remove a relative cache state is based on rest of the relative cache states in the set and the type of the analysis (worst/best). We explain the decision process as follows:

Worst case A cache state cs r k is subsumed by cs r j , if for all cache lines (c i ∈ C), when the relative instruction in cs r j is same as the instruction in cs r k (cs r j

or, the relative instruction in cs r j captures a cache miss (cs r j [i] = 1).

For the example in Table 8, for the first three cache line (c 0 , c 1 , c 2 ) the relative instructions in cs r 2 and cs r 1 are same. However, for the cache line c 3 , cs r 2 [3] = 1 and cs r 1 [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = 0. Thus, cs r 1 is subsumed by cs r 2 .

Best case A cache state cs r k is subsumed by cs r j , if for all cache lines (c i ∈ C), when the relative instruction in cs r j is same as the instruction in cs r k (cs r j

or, the relative instruction in cs r j captures a cache hit (cs r j [i] = 0). For the example in Table 8, for the first three cache line (c 0 , c 1 , c 2 ) the relative instructions in cs r 2 and cs r 1 are same. However, for the cache line c 3 , cs r 2 [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = 1 and cs r 1 [START_REF] Falk | Optimal static WCET-aware scratchpad allocation of program code[END_REF] = 0. Thus, cs r 2 is subsumed by cs r 1 .

The overview of the new approach is presented in Figure 17(b). Given a cache model CM , we optimise the current UoA join function (Definition 17) by creating two new join functions to analyse the best and worst cases. These two functions are described by the following definitions.

Definition 23 (UoA join function for worst case). The worst case UoA join function J U oA +w : 2 CS r × 2 CS r → 2 CS r where for any two relative cache states

where, S U oA +w : CS r × CS r → {true, f alse} where, for any cs r 1 , cs r 2 ∈ CS r ,

Definition 24 (UoA join function for best case). The best case UoA join function J U oA +b : 2 CS r × 2 CS r → 2 CS r where for any two relative cache states CS r 1 ∈ 2 CS r and CS r 2 ∈ 2 CS r , J U oA +b (CS r 1 , CS r 2 ) = CS r 3 where,

where, S U oA +b : CS r × CS r → {true, f alse} where, for any cs r 1 , cs r 2 ∈ CS r ,

2 ) we first check for subsumed unknown (⊥) relative cache states using J U oA (CS r 1 , CS r 2 ). In this case, In Figure 14,

The UoA join function Given CS r

The UoA transfer function

UoA join function for worst case

UoA join function for best case

Table 10: Some of the symbols and the definitions presented in this section.

Inria 7 Comparisons between the NUS, Absint and UoA approaches

In this section, we compare the three approaches by comparing their computed concrete reaching cache states and the precision. The NUS approach directly computes the concrete reaching cache states of a block, during its fixed point computation (Algorithm 1). The Absint approach computes the abstract reaching cache states and then maps them into the concrete cache states, using the mapping function M AP Absint (Definition 13). Similarly, the proposed approach computes the reaching relative cache states of a block using the fixed point computation (Algorithm 5). However, we have not yet described how the relative cache states are mapped into the concrete cache states. We need this mapping to facilitate a better comparison between the three approaches.

We start by presenting a function that maps the relative cache states to the concrete cache states (in Section 7.1). Later, we present a detailed comparison between the three approaches (in Section 7.2).

Mapping relative cache states of b ref to concrete cache states

In this section, we present how the reaching relative cache states for the reference block can be converted into concrete reaching cache states. The mapping function, called M AP U oA , is defined in Definition 27. However, the following notions/definitions are essential to describe the mapping function.

A relative cache state cs r is a vector [inst r 0 , inst r 1 , . . . , inst r N -1 ] and for each cache line c i ∈ C, inst r i ∈ {×, 0, 1, , ⊥}. Here, each element inst r i is described in relation to the instruction on cache line c i (BI(b ref ) [i]) in the block b ref . These relations can be translated into a set of constraints. We explain these constraints as follows.

• inst r i = × describes that the instruction on the cache line c i is unconstrained. The instruction in the cache line c i can be any possible instruction from the set CI(c i ) or can be empty ( ). E.g., given CI(c 0 ) = {m1, m5} and inst r 0 = ×, then the instruction on cache line c i could represent any instruction from { } ∪ CI(c 0 ) = {m1, m5, }.

• inst r i = 0 describes the constraint that the instruction in the cache must be BI(b ref ) [i]. E.g., given inst r 0 = 0 and BI(b ref )[0] = m1, then the only possible instruction in cache line c 0 is m1.

describes that there is no instruction ( ) on the cache line c i . E.g., given inst r 0 = , then there is no instruction on cache line c 0 . It is empty ( ).

• inst r i = ⊥ describes that there is an instruction on the cache line c i and it must belong to the set (CI(c i )). E.g., given CI(c 0 ) = {m1, m5} and inst r 0 = ⊥, then the instruction in cache line c 0 could represent any instruction from {m1, m5}.

Hence, given a cache model CM , a cache line c i ∈ C, an element of the relative cache state (inst r i ) and, the reference block b ref , we can compute the corresponding set of possible concrete instructions, for the cache line c i . This computation is described using the following function.

Definition 25 (Relative instruction to concrete instructions mapping). Given a cache model CM and the reduced graph G r = B r , b init , E r , the relative instruction to concrete instructions mapping function M AP inst U oA : C × {×, 0, 1, , ⊥} × B r → 2 I∪{ } where, for a given cache line c i ∈ C, a relative instruction inst r i ∈ {×, 0, 1, , ⊥}, and a block b ∈ B r .

Illustration

Using Table 11, we illustrate the function M AP inst U oA . For the cache line c 0 , given that the instruction executed by the block b ref is m1 (BI(b ref )[0] = m1) and CI(c 0 ) = {m1, m5}, for each possible relative instruction inst r 0 , we describe the mapping as follows. • inst r 0 = 1 (row 3) describes the instruction on the cache can not be m1,

• inst r 0 = (row 4) describes the instruction on the cache is empty,

As discussed above, a relative instruction inst r i could map to more than one instruction. For the cache model presented in Figure 2 (running example), given a relative cache state cs r = [×, 1, 0, 0], the reference block with BI(b ref ) = [∓, m6, m3, m4], for cache lines c 0 , c 1 , c 2 , c 3 using the mapping function M AP inst U oA , we get the sets { , m1, m5}, { , m2}, {m3}, {m4} respectively.

This represents that c 0 contains , m1, or m5, c 1 contains or m6, c 2 contains m3, c 3 contains or m8. We can describe this as the abstract cache state (described in Definition 10)

Contents

List of Figures Computing all possible abstract reaching cache states using the Absint approach.