Ikram Senoussaoui

Contention-free scheduling of PREM tasks on partitioned multicore platforms

Commercial-off-the-shelf (COTS) platforms feature several cores that share and contend for memory resources. In real-time system applications, it is of paramount importance to correctly estimate tight upper bounds to the delays due to memory contention. However, without proper support from the hardware (e.g. a real-time bus scheduler), it is difficult to estimate such upper bounds.

This work aims at avoiding contention for a set of tasks modeled using the Predictable Execution Model (PREM), i.e. each task execution is divided into a memory phase and a computation phase, on a hardware multicore architecture where each core has its private scratchpad memory and all cores share the main memory. We consider non-preemptive scheduling for memory phases, whereas computation phases are scheduled using partitioned preemptive EDF. In this work, we propose three novel approaches to avoid contention in memory phases: (i) a task-level time-triggered approach, (ii) job-level time-triggered approach, and (iii) on-line scheduling approach. We compare the proposed approaches against the state of the art using a set of synthetic experiments in terms of schedulability and analysis time. Furthermore, we implemented the different approaches on an Infineon AURIX TC397 multicore microcontroller and validated the proposed approaches using a set of tasks extracted from well-known benchmarks from the literature.

I. INTRODUCTION

Modern commercial-off-the-shelf (COTS)-based embedded systems include multiple active components (such as CPU cores and I/O peripherals) that share and contend for memory resources. They are likely subject to contention and require a particular attention when supporting hard real-time constraints.

Contention on memory resources has received much attention in the real-time community [START_REF] Alhammad | Time-predictable execution of multithreaded applications on multicore systems[END_REF], [START_REF] Maia | Schedulability analysis for global fixed-priority scheduling of the 3-phase task model[END_REF], [START_REF] Rosen | Bus access optimization for predictable implementation of real-time applications on multiprocessor systems-on-chip[END_REF], [START_REF] Tabish | A real-time scratchpad-centric os with predictable inter/intra-core communication for multi-core embedded systems[END_REF], [START_REF] Yao | Memory-centric scheduling for multicore hard real-time systems[END_REF]. Two approaches are popular: (i) estimating the worst-case interference profiles and deriving safe execution time bounds; (ii) avoiding interference at the system design level. In the first approach, the hardware platform and the task execution must be modeled accurately: the memory access profiles of all tasks are extracted and combined with each other to estimate the worst-case profile. In general, it is difficult to precisely compute the worst-case interference profile, which likely leads to include scenarios that might never occur, therefore overestimating the worst-case interference. The second approach tends to prevent interference by enforcing time isolation (e.g. time partitioning schemes like MemGuard [START_REF] Yun | Memory bandwidth management for efficient performance isolation in multi-core platforms[END_REF]).

An intermediate approach is to use appropriate application models such as the Acquisition-Execution-Restitution model (AER) [START_REF] Durrieu | Predictable flight management system implementation on a multicore processor[END_REF], or the PRedictable Execution Model (PREM) [START_REF] Pellizzoni | A predictable execution model for cots-based embedded systems[END_REF]. In the latter, a task is modeled by two distinct phases: a memory phase and computation phase. In the memory phase, data is exchanged between main memory and local memory. This includes write-back of the computed data from the local memory to main memory of the previous job, and fetching new data for the activated job from the main memory to the local memory. In a computation phase, loaded data is processed and all access to the main memory is forbidden.

Finding the proper way of scheduling memory phases is not straightforward. One difficulty is the lack of hardware support for real-time scheduling on the bus. Typical bus controllers available on commercial platforms support very simple policies like First-In-First-Out or slot-based time-triggered scheduling. FIFO safe-response time bounds are known to be very large, whereas fixed slots are not flexible enough to efficiently support the variety of application requirements. The problem is even more complex, as the respect of timing constraints requires to tightly co-schedule and analyze the memory phases that are achieved on the bus, and compute phases that are executed on the different cores.

We believe that the use of hardware platforms featuring private scratchpad memory at core level and a global memory, with software modeling techniques like PREM is essential to build efficient and predictable real-time systems.

Contributions.: In this paper, we explore and compare different designs for scheduling memory phases: a timetriggered memory schedules approach and an on-line scheduled memory phases approach. In all the proposed approaches, we always consider preemptive partitioned scheduling at the core level for computations phases. Therefore, the contributions of this paper are the following:

(i) Task-level time-triggered approach : an artificial activation time (offset) is computed for all jobs of a given memory phase, such that no memory phase will overlap with another at runtime. We present novel sufficient schedulability tests to assign task-level offsets to the memory and computation phases so that all deadlines are met. We propose as well an integer linear program (ILP) to compute the optimal offsets; (ii) job-level time-triggered approach: different artificial activation times (offsets) can be set to different jobs of the same memory phase. We assign these offsets by revising ILP of task-level offsets; (iii) on-line approach: where memory phases are assigned appropriate intermediate deadlines and scheduled on the bus using EDF. In this way, we decouple the problem of scheduling on the bus from the core scheduling.

In particular, we propose a new heuristic to compute the values of these intermediate deadlines; (iv) we provide a large set of experimental evaluations showing the effectiveness of our algorithms, and improving up to 50% the schedulability compared to equivalent schedules generated with the state-ofthe-art methods [START_REF] Arora | Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF];(v) we experimentally demonstrate the applicability of our methodology on the Infineon AURIX TC-397 multicore family of processors using different benchmarks.

II. RELATED WORK

Over the last years, several scheduling methods for COTSbased multicore systems have been presented to deal with the problem of memory contention.

Most COTS architectures feature a single port main memory that is shared among all CPU cores and peripherals. Multiple cores can run multiple threads, each of which generates memory requests, hence, estimating memory-contention safe delays is very difficult because each memory request is likely to be interfered by other requests. Pellizzoni et al. have shown in [START_REF] Pellizzoni | Worst case delay analysis for memory interference in multicore systems[END_REF] that the worst-case execution time (WCET) of a task increases linearly with the number of suffered cache misses, due to contention for access to main memory. New task execution models that make use of pre-fetching techniques have been proposed in the literature [START_REF] Rosen | Bus access optimization for predictable implementation of real-time applications on multiprocessor systems-on-chip[END_REF]. The authors of [START_REF] Adzer Hoogeveen | Preemptive scheduling in a two-stage multiprocessor flow shop is nphard[END_REF] show that pre-fetching techniques improve the cache/scratchpad locality and reduce average execution times.

PREM (PRedictable Execution Model) was introduced in [START_REF] Pellizzoni | A predictable execution model for cots-based embedded systems[END_REF] to co-schedule both memory requests from CPU and I/O with computations on uniprocessor platforms with multilevel caches. In this model, tasks are modeled in two phases: (i) a memory phase where all data are transferred from/to the main memory to/from a local memory, and (ii) a pure execution phase where the loaded data are processed. The model greatly reduces the variability of memory-contention latency by explicitly controlling memory accesses during memory phases. In [START_REF] Yao | Memory-centric scheduling for multicore hard real-time systems[END_REF], PREM has been extended to partitioned multicore/processor platforms, where isolation is provided through a coarse-grained TDM memory schedule. The scheduling policy of each core favors the priority of its pending memory phases above computation phases in order to ensure better utilization of the TDMA slots. The Acquisition-Execution-Restitution model (AER) [START_REF] Durrieu | Predictable flight management system implementation on a multicore processor[END_REF] is an extension of the PREM model where each task is modeled by 3 phases, two memory phases (reading and writing) and a computation phase.

In [START_REF] Becker | Contention-free execution of automotive applications on a clustered many-core platform[END_REF], Becker et al. presented an approach to timetriggered scheduling for automotive runnables on a manycore platform. Memory bank privatization is used to avoid contention between memory accesses from different cores. Each core has a private memory bank, similar to a scratchpad, and runnables are assumed to have read-execute-write phases (AER model). The scheduling algorithm executes each runnable non-preemptively, and ensures that accesses to the shared memory bank made in read and write phases do not overlap, thus avoiding contention on the shared bus. The task allocation problem is formulated as an Integer Linear Programming (ILP) problem, whose solution is the optimal time-triggered schedule for the on-core execution as well as for the access to shared memory.

Recent research on memory-centric scheduling is presented in [START_REF] Schwäricke | Fixed-priority memory-centric scheduler for cots-based multiprocessors[END_REF]. The authors proposed a fixed-priority memory-centric scheduler for predictable memory management on COTS multiprocessor platforms without the need for any hardware support. The work in [START_REF] Arora | Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF] focuses on bus contention for the 3-phases task models and assumes First-Come First-Served (FCFS) bus arbitration. Works in [START_REF] Arora | Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF], [START_REF] Becker | Contention-free execution of automotive applications on a clustered many-core platform[END_REF], [START_REF] Schwäricke | Fixed-priority memory-centric scheduler for cots-based multiprocessors[END_REF] are the closest to the first part of our work. The main differences are as follows: 1) we assume that the task to core allocation is given; 2) instead of using a time-triggered schedule for both the core scheduling of computation phases and the bus scheduling of memory phases, we schedule the memory requests using a time-triggered scheduler and the computation phases using an event-based scheduler, thus simplifying the ILP problem; 3) we allow preemption between computation phases, whereas the works in [START_REF] Becker | Contention-free execution of automotive applications on a clustered many-core platform[END_REF], [START_REF] Schwäricke | Fixed-priority memory-centric scheduler for cots-based multiprocessors[END_REF] consider a non-preemptive scheduler on all levels (cores and communication bus); 4) finally, [START_REF] Arora | Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF] uses fixed-priority scheduler, whereas we use EDF scheduling for cores.

In this paper, our second contribution is to use an on-line scheduler for the bus, by assigning intermediate deadlines to memory phases. One of the most effective techniques to schedule dependent tasks on multicore platforms is to assign intermediate deadlines and offsets in order to enforce precedence constraints [START_REF] Houssam-Eddine | The hpc-dag task model for heterogeneous real-time systems[END_REF]. The advantage of such technique is that a set of dependent tasks (phases) is converted into a set of independent tasks with offsets, for which well-known and efficient schedulability analyses exists. The most popular heuristic algorithms are fair distribution and proportional distribution [START_REF] Zahaf | Preemption-aware allocation, deadline assignment for conditional dags on partitioned edf[END_REF]. Baruah et al. [3] suggested an approach to assign shorter relative deadlines to a set of tasks without violating the feasibility of the system. We will start from this idea to develop a complete heuristic technique to search for sub-optimal set of intermediate deadlines.

III. SYSTEM MODEL A. Architecture model

In this work, we consider a multicore platform composed of m cores. Each core has a single local scratchpad memory. Memory copy operations between main and scratchpad memories are performed via a shared bus. The tasks explicitly trigger memory copies between main and scratchpad memories before starting the computation. In many cases, this separation of code between memory phase and computation phase can be performed automatically, for example when compiling code from high-level programming languages like Prelude [START_REF] Fort | Code generation for multi-phase tasks on a multi-core distributed memory platform[END_REF], or by modifying existing compilers [START_REF] Muhammad | Prem-based optimal task segmentation under fixed priority scheduling[END_REF]. We assume that the separation between the two phases has been done either manually by the programmer, or by an appropriate code generation tool.

Figure 1 depicts a multicore platform with 4 cores. Each core is directly connected to its own scratchpad memory and to the main memory. We assume that all memory (main memory and local scratchpads) is directly accessible to all cores via different address spaces. An example of such architecture is the Infineon Aurix TC397 [START_REF] It | Aurix 32-bit microcontrollers for automotive and industrial applications[END_REF].

B. Task model

Let T = {τ 1 , τ 2 , • • • , τ n }
be a set of n periodic tasks. Each task τ i has two phases: (i) a memory phase in which all data required (resp. produced) by τ i is loaded (resp. stored) in memory, and (ii) a computation phase where preloaded data is processed, without any access to the main memory. The computation phase is not allowed to start before the completion of the memory phase. Therefore, task τ i is characterized by the tuple τ i = (M i , C i , D i , T i ), where:

• M i is the task worst-case memory access time. It represents an upper bound to the time during which the task τ i perform data transfers from/to memory and/or I/O devices. Once this phase starts, it cannot be preempted. • C i is the task worst-case computation time. In contrast to the memory phase, the computation phase can be preempted. • D i is the task's relative deadline. Each instance of task τ i must finish its execution no later than D i time units after its activation. • T i is the task period, it represents the exact time interval between two consecutive activations of τ i . We consider strictly periodic tasks. We denote by u m i = Mi Ti (resp. u c i = Ci Ti ) the memory phase (resp. computation phase) utilization. Therefore, the task utilization is given by U i = u m i + u c i and the total utilization of task set T is computed as

U T = n i U i .
We denote by H the task set hyperperiod, i.e. the system's period. It is defined as the least common multiple between all periods of tasks H = LCM (T 1 , T 2 , • • • , T n ). Each task τ i generates an infinite sequence of jobs, however the pattern repeats every H intervals. Therefore, we are interested in the set of released jobs J i between time instance 0 and H, i.e.

J i = {j 0 i , j 1 i , • • • , j H T i i }. Each job j l i is released exactly at time instant a l i = l•T i and must complete no later than d l i = a l i +D i . IV. OFFSET-BASED PROCESSOR/MEMORY CO-SCHEDULING
In this work, we tackle the bus contention problem by avoiding conflicting bus access altogether. In this first part, we assign offsets to memory phases so that they do not overlap at run time, while all deadlines are met.

The task model with offsets is exemplified in Figure 2. We denote by ϕ(M h ) the memory offset of job j h . By design, memory phases will never compete with each other on the bus, therefore every memory phase starts its execution exactly at ϕ(M h ) time instant from its activation a h . The computation phase of job j h becomes ready to execute exactly at time ϕ(C h ) = a h +ϕ(M h )+M h , called computation offset, regardless of the actual transfer time of the memory phase. In other words, the computation phases are activated by a timer programmed to fire an interrupt at ϕ(C h ). In this way, we can schedule computation phases on the different cores separately from the memory phase, using classical single core scheduler and classical single core analysis in the presence of offsets to assess schedulability (Section IV-A1).

Dh Th In this work, we consider two types of memory phases offsets : task-level and job-level offsets. In the first, all jobs of the same task have the same offset, while in the second approach, different job of the same task might have different offsets.

M h C h a h ϕ(M h ) ϕ(C h ) d h

A. Task-level offsets : sufficient condition

In the following, we present a technique to assign a fixed offset to the memory phase of a task, so that all jobs of the tasks will have the same offset, and all deadlines are met.

Theorem 1 (Jan Korst et al [START_REF] Korst | Periodic multiprocessor scheduling[END_REF]). Let τ 1 and τ 2 be two periodic tasks. τ 1 and τ 2 can be scheduled on the same core, without any overlap if and only if :

gcd(T 1 , T 2 ) ≥ C 1 + C 2 (1)
Where gcd is the greatest common divisor of T 1 and T 2 .

The schedulability test of Theorem 1 allows to execute two tasks without any overlap. It is extended in to support tasks with offsets in [START_REF] Korst | Periodic multiprocessor scheduling[END_REF] as follows :

Lemma 1. Let τ 1 , τ 2 be two periodic tasks having offsets ϕ(τ 1 ) and ϕ(τ 2 ) respectively, τ 1 and τ 2 can be scheduled on the same core, without any overlap if and only if:

C 1 ≤ (ϕ(τ 2 ) -ϕ(τ 1 )) mod gcd(T 1 , T 2 ) ≤ gcd(T 1 , T 2 ) -C 2 (2)
We use Lemma 1 to compute the offsets of the different memory phases.

Lemma 2. A set of periodic memory phases

M = {M 1 , M 2 , • • • , M n } can be scheduled without any overlap if: gcd(T 1 , T 2 , • • • , T n ) ≥ n i=1 M i (3)
Proof. Since the minimum time distance between any activation time of any task τ i and the successive activation time of another task τ j is a multiple of the gcd of the task periods, then, if

gcd(T 1 , T 2 , • • • , T n ) ≥ n i=1
M i all memory phases can be executed in interval of τ i and τ j , which proves the sufficiency of 3.

Theorem 2. Let T be a set of n periodic tasks and let M = {M 1 , M 2 , • • • , M n } their memory phases. The time distance between any activation time of a memory phase M i and its release time (the start time of M 1 = 0) so that any two memory phases do not overlap can be computed as follows:

ϕ(M j ) ∈   j-1 i=1 M i , g - n i=j+1 M i   (4)
Where

g = gcd(T 1 , T 2 , • • • T n ).
Proof. From Lemma 2, it is sufficient that the sum of all memory phases to be less or equal to the gcd, so to schedule memory phases without overlapping. Therefore, it is sufficient to find any distribution of the bus-time equal to the gcd of task periods. By choosing the offsets (tasks are in any arbitrary order): ϕ(M j ) = j-1 i=1 M i and ϕ(M 1 ) = 0 we can garantee the non overlapping of all memory phases, having Equation (4).

According to Theorem 2, to compute the task-level offsets, it suffices to compute the sum of the length of all memory phases. If it does not exceed the gcd of the periods of all tasks, then the offsets can be easily In this paper, we order tasks in a non-decreasing order of relative deadline, therefore they get the smallest memory phase offset, to maximize the slack time to computation phases. Of course, this may be very pessimistic, and many schedulable tasks sets cannot be assigned task-level offsets in this way. A better solution will be proposed in the following.

1) Scheduling analysis of computation phases: To schedule computation phases on cores, we use the Earliest Deadline First algorithm (EDF). Our analysis is based on the processor demand criterion [START_REF] Sanjoy K Baruah | Algorithms and complexity concerning the preemptive scheduling of periodic, realtime tasks on one processor[END_REF], [START_REF] Pellizzoni | Feasibility analysis of real-time periodic tasks with offsets[END_REF] and considers only computation phases with offsets. The processor demand function for computation phases with offsets is defined as follows:

df (t 1 , t 2 ) = n i=1 ∆ i (t 1 , t 2 ) • C i (5)
Where:

∆ i (t 1 , t 2 ) = t 2 -ϕ(C i ) -D i T i - t 1 -ϕ(C i ) T i + 1 (6)
It is the amount of time demanded by the tasks (computation phases) in interval [t 1 , t 2 ) that the core must execute to ensure that no task misses its deadline. Considering a fully preemptive single core scheduler, a necessary and sufficient condition for a set of tasks (computation phases) to be schedulable by EDF consists in checking that the demand never exceeds the length of the interval.

Lemma 3. (Baruah et al. [START_REF] Sanjoy K Baruah | Algorithms and complexity concerning the preemptive scheduling of periodic, realtime tasks on one processor[END_REF]). The taskset T is feasible on a single core (U T ≤ 1) if and only if:

∀0 ≤ t 1 < t 2 ≤ H, df (t 1 , t 2 ) ≤ t 2 -t 1 (7)
B. Integer-Linear-Programming-Based offset assignment In this section, we present a modular ILP design that is able to compute both task-level and job-level offsets.

The ILP must verify the following properties : (i) a schedule is found for all memory phases (prop1), (ii) two memory phases do not overlap on the bus (prop2), (iii) each memory phase receives sufficient bus-time to complete (prop3), and (iv) the schedulability of the different computation phases is granted (prop4).

1) Property prop1 (task-level and job-level offsets): The output of our ILP is the set of all memory phases offsets, or fail if no solution can be found. Our ILP is optimal, therefore if a solution exist, it will not fail. We define decision variable ϕ(M j ) as the offset of the memory phase for job j. Our ILP builds τi∈T H Ti decision variable of type ϕ(M j ), representing offsets of all jobs, verifying therefore Property prop1.

Our ILP is able to build both task-level and job-level offsets by manipulating offsets decision variables as follows:

1) Task-level offsets. To enforce the ILP to select tasklevel offset, we set the offset decision variable of all jobs of the same task to be equal, as in Equation ( 8).

One may even replace all appearances of ϕ(M j ), for every job of task τ by a single decision variable ϕ(τ ), avoiding therefore to generate a variable per job per task. For sake of simplicity, and without loss of optimality for task-level offsets, we consider the first option, that is:

∀i ∈ n, ∀j ∈ [1 • • • H Ti ], ϕ(M j+1 ) -ϕ(M j ) = 0 (8) 2)
Job-level offsets. To enforce the ILP to select job-level offset, we relax the constraints of Equation ( 8), therefore the ILP is free to select different offsets for different jobs of the same task. 2) Properties prop2 and prop3 (Non-overlapping and sufficiency constraints): We introduce new constraints to verify Property prop2. The memory phase of job j starts at ϕ(M j ) and completes exactly at ϕ(M j )+M j . During this interval, we must ensure that memory phase of any other job h cannot start or complete within [a j +ϕ(M j ), a j +ϕ(M j )+M j ). Therefore, job h memory interval either completes before a j + ϕ(M j ) (case 1), or starts later to a j +ϕ(M j )+M j (case 2). Therefore, for every couple of jobs of different tasks, we introduce 2 new binary decision variables x jh , and y jh verifying which case the ILP solver has selected, as defined in Equations ( 9), [START_REF] Adzer Hoogeveen | Preemptive scheduling in a two-stage multiprocessor flow shop is nphard[END_REF].

x jh = 1 , if a h + ϕ(M h ) + M h ≤ a j + ϕ(M j ) 0 , otherwise (9)
or

y jh = 1 , if a j + ϕ(M j ) + M j ≤ a h + ϕ(M h ) 0 , otherwise (10)
Due to the mutual exclusion of both cases, the above constraints are not linear. Equation [START_REF] Houssam-Eddine | The hpc-dag task model for heterogeneous real-time systems[END_REF] shows linearization of these constraints:

(a j + ϕ(M j )) -(a h + ϕ(M h ) + M h ) -R • x jh ≤ 0 (a j + ϕ(M j )) -(a h + ϕ(M h ) + M h ) + R • (1 -x jh ) ≥ 0 (a h + ϕ(M h )) -(a j + ϕ(M j ) + M j ) -R • y jh ≤ 0 (a h + ϕ(M h )) -(a j + ϕ(M j ) + M j ) + R • (1 -y jh ) ≥ 0 x jh + y jh = 1
where R is a large positive integer. [START_REF] Houssam-Eddine | The hpc-dag task model for heterogeneous real-time systems[END_REF] These constraints do not only allow to verify Property prop2, but as well Property prop3. It enforces all memory phases other than the one of job j to start no earlier to the completion of the memory phase of j.

3) Property prop4 (Feasibility constraints): We guarantee the respect of timing constraints for the EDF scheduling on every core, by incorporating the offsets induced by the memory phases to the classical processor demand schedulability analysis within our ILP. The exact condition for a set of jobs to be scheduled by EDF within the interval I = [t 1 , t 1 ] is that the cumulative computation time of all jobs with release time greater than or equal to t 1 and deadline less than or equal to t 2 not exceed the length of the interval |I|.

In order to avoid checking the schedulability for all values of t 1 and t 2 with a high complexity, we check only the intervals where the demand function might change. That is, we verify all intervals where t 1 is selected in the set of computation release offsets i.e. t 1 ∈ {∀j, a j +ϕ(M j )+M j } and t 2 is selected from the set of absolute deadlines i.e. t 2 ∈ {∀j, d j }. We denote t 1 as t(j) (referring to the start time of computation phase of job j) and t 2 as d(h) (referring to the absolute deadline of job h).

Therefore, for every couple of t(j) and d(h) and for every job l, we introduce the decision variable z l,j,h that expresses if job l is released and has its absolute deadline in the interval [t(j), d(h)]. As we consider partitioned scheduling, j and l must be allocated to the same core without loss of optimality:

z l,j,h = 1, if t(j) ≤ a l + ϕ(M l ) + M l and d(h) ≥ d l 0, otherwise (12)
As before, we linearize the evaluation of z l,j,h , and replace t(j) by its value as follows:

(a l + ϕ(M l ) + M l ) -t(j) -R • z l,j,h ≤ 0 (a l + ϕ(M l ) + M l ) -t(j) + R • (1 -z l,j,h ) ≥ 0 (13)
The feasibility can be tested for all the intervals by computing the cumulative execution time for every couple of t(j) and d(h) using the following constraints:

∀t(j) ∈ {∀j,a j + ϕ(M j ) + M j } ∀d(h) ∈ ∀h, d h l C l • z l,j,h ≤ (d(h) -t(j)). (14)
Jobs are sorted by deadlines, so that every job is considered in only a single couple, reducing the number of the constraints without loss of optimality. Objective function. A realisable solution allows to respect all the constraints defined in our ILP. Therefore, it is not mandatory to our ILP to define an objective function as any realisable solution can be accepted from real-time perspective. Therefore, our objective function can be set to 0, so that solvers will stop at the first solution respecting all constraints making the ILP faster. We can as well set the objective function to minimize as much as possible the memory phases offsets, as follows:

Minimize

i∈n,j∈Ji ϕ(M j ) (15)
Once the ILP has been formulated, it is submitted to the CPLEX ILP-solver ( [START_REF]CPLEX User's Manual. Ibm cplex optimization studio[END_REF]).

V. DEADLINE-BASED PROCESSOR MEMORY CO-SCHEDULING

The ILP-based approaches proposed in the previous section find the optimal solution when a feasible one exists. Unfortunately, they suffer from high computational complexity. For this reason, we followed a different approach to manage contention on the memory bus. The basic idea is to have a centralized yet partitioned scheduler, located on one of the cores, which performs the data transfers from/to local scratchpads according to an on-line scheduling algorithm. We consider data transfers as non-preemptive tasks, each one with a period and an intermediate deadline, to be scheduled on the single resource "bus" by a non-preemptive on-line scheduler (EDF). These assigned intermediate deadlines δ i are used as offsets for scheduling computation phases on the cores.

The main difference with the ILP-based scheduling of memory phases is that the ILP assigns "slots" to memory phases, each slot is an interval of size equal to the length of the data transfer, while the deadline-based approach assigns interval which may be larger than the length of the data transfer, and memory phases are scheduled as non-preemptive tasks with an on-line single core policy. The system is correct, if all memory phases respect their intermediate deadline, and that the computation phase respect the task deadline with the intermediate deadline of memory phase as an offset.

For every phase, the intermediate deadline δ i must be greater than the memory phase duration M i , considered as a lower bound, and no greater to D i -C i , considered as an upper bound. Setting the intermediate deadline to the lower bound will enforce every memory phase to start its execution at its arrival, otherwise it misses its deadlines. Setting the deadline to the upper bound D i -C i will enforce the computation phase to start its execution at its activation. The problem is to find a compromise between the slack time assigned to both memory and computation phase for every task.

Algorithm 1 implements a binary search technique to assign the intermediate deadlines to the memory phases. Therefore, lower bound lb i and upper bounds ub i are computed for every task (Line 2). Then, the algorithm sets the intermediate deadlines to the middle between lb i and ub i (Lines 4-8). Further, the non-preemptive schedulability test for EDF is applied [START_REF] Jeffay | On non-preemptive scheduling of periodic and sporadic tasks[END_REF], to assess the feasibility on the bus (Line 9). If the set of memory phases is schedulable on the bus using the computed intermediate deadlines, schedulability is checked on all cores, using Pellizzoni and Lipari [START_REF] Pellizzoni | Feasibility analysis of real-time periodic tasks with offsets[END_REF] approximate test with pseudo-polynomial complexity (Line 11). In the case of success, Algorithm 1 exists on SUCCESS. If the schedulability on cores fails, it modifies only the intermediate deadlines of the tasks that are allocated on the cores that were deemed not schedulable by assigning shorter deadlines to the memory phases (moving the upper bounds to the computed intermediate deadlines -Line 14). Further, we iterate until the system is schedulable on both bus and cores. If the schedulability fails on the bus, the intermediate deadlines are increased by setting the lower bounds to the intemediate deadlines (Line 17). When the upper bounds and the lower bounds are equal, the binary search fails to find a feasible schedule for both bus and cores and Algorithm 1 exits on FAIL.

Algorithm 1 Binary search guided by core schedulability 1: Input T : set of tasks 2: ∀τ i ∈ T :

lb i ← M i ; ub i ← D i -C i ; 3: repeat 4:
S ← ∅ {The set of memory phases} 5:

for τ i ∈ T do 6: if dbf analysis np(S) then 10:

δ i ← ubi+lbi
∀τ i ∈ T : ϕ(C i ) ← δ i 11:
if dbf offset analysis(T ) then

∀τ i ∈ T : lb i ← δ i 18:
end if 19: until ∀τ i ∈ T : ub i = lb i 20: return FAIL

VI. RESULTS AND DISCUSSIONS

In this section, we present the performances of the proposed approaches with respect to the state of the art. First, we conducted experiments with randomly generated workloads to evaluate the proposed approaches using different task partitioning heuristic. We study the impact of the task memory stall ( Mi Ci+Mi ) and the workload size on schedulability and the required time to complete the analysis. We compared the proposed approaches with a similar analysis from the state-ofthe-art [START_REF] Arora | Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF]. Finally, we evaluate the practicality of the proposed approaches and the overall system performances with a set of real benchmarks running on the Infineon Aurix TC397 microcontroller.

A. Task set generation

The synthetic task set generation takes as input n the number of tasks and the target total utilization U T . It starts by generating the utilizations of the n tasks by using UUniFast-Discard [START_REF] Emberson | Techniques for the synthesis of multiprocessor tasksets[END_REF] algorithm. We varied the baseline utilization from 0.4 to P (number of available cores) with a step of 0.2. For every utilization U i , the algorithm generates the memory phase utilization u m i using a random stall value. The random value is either selected in lev 1 = [0.10, 0.20] or in lev 2 = [0.20, 0.30] according to the selected scenario. The generated utilization comprises computation and memory phases, therefore the total computation utilization on the cores is smaller than U T . For each scenario, we generate 100 task sets per utilization and per memory stall. We generate 10 tasks per taskset for the offset-based approaches. As their complexity is high, they are evaluated under limited settings. For heuristic approaches, we generate 32 tasks per taskset. To avoid intractable hyperperiods, the period of every task is selected randomly from the list of periods : {80,100,200,240,400,600,800,1200}. When memory phase utilization is very low, periods are multiplied by 10, so that every task have at least M i greater or equal to 1. The task deadline is set to 70% of the task's period.

B. Results of synthetic task set experiments

In this section, we evaluate the performance of three offset based methods against our heuristic (Algorithm 1): the tasklevel offset (Theorem 2) denoted as SO; the ILP-based tasklevel offset denoted as ILP-SO, and the job-level offset denoted as ILP-JO. The tasks are allocated on 4 cores by either Worstfit (WF) or Best-fit (BF). Therefore, each algorithm is labeled by a combination of these techniques. In Figure 3, we report the schedulability ratio as a function of total utilization for the two classes of memory stalls. Consistently with previous results in the literature, WF outperforms BF in all simulated scenario, therefore, we only report the results for WF for clarity of presentation. At low total utilization values, all algorithms easily schedule all tasks sets. As the utilization increases, the ILP-based offset assignment algorithms outperform the task-level offset assignment algorithm. We remark that, given a task allocation, ILP for job-level offset is a relaxed version of the ILP at task-level, therefore, it naturally outperforms the latter. The schedulability falls sharply for WF-SO algorithm because Condition 3 becomes quickly not satisfied for large memory phases. Please notice, that our intermediate deadlines approach performances are still very acceptable regarding the ILP-based approaches in terms of schedulability, even with their hugely shorted analysis time compared to ILP approaches. Indeed, each simulation using ILP takes around 3 hours to complete on a 40-cores Intel(R) Xeon(R) CPU E5-2630 v4 at 2.20GHz, with 130 GB of RAM using CPLEX ILP solver. In the other hand, the analysis time of WF-ILP-SO is acceptable (i.e. a few seconds). The difference between the ILP and our heuristic is even reduced when the stall is larger. Naturally, the schedulability of tasklevel offset based sufficient test falls sharply as total utilization (i.e. memory phases length increase). Our heuristic (Algorithm 1) is compared to related work on large settings composed of 32 tasks. The results in terms of schedulability and required analysis time are reported in Figure 4. We simulated two different memory stalls [0.1-0.2) (denoted as 0.1) and stall [0.2 -0.3) (denoted as 0.2). We compare our heuristics against the response time analysis for FIFO-bus scheduler and fixed priority core scheduler found in [START_REF] Arora | Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF], (denoted as FP in the algorithm label). As the utilization increases, the WF algorithms present better performances in terms of schedulability than BF algorithms, for [START_REF] Arora | Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF] and our approaches. Therefore, we kept only the best results of BF algorithm, which is using our heuristic (BS) at stall [0.1-0.2).

Our heuristic algorithms perform much better than the approach analyzed in [START_REF] Arora | Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF], especially when workload is high. Our algorithm has pseudo-polynomial complexity, however, their run-time is acceptable even for large task sets as shown in Figure 4b. Please observe that the memory stall has an impact on schedulability as it drops sharply, when the latter increases.

VII. PERFORMANCES ON REAL PLATFORM

We demonstrate the applicability of our methodology on the popular Aurix Tricore platform by Infineon. We use the TC397 TFT board, that features 6 cores indexed from 0 to 5. Each core has its own data and program scratchpads. Data scratchpads of cores 0 and 1 are larger than those of the other cores. However, for simplicity, in this work we consider all scratchpads of the same size. Therefore, only 96 KB of data scratchpad is used on each core. All cores share the main memory of size 768 KB. Data are transferred between the different memories using a single DMA channel on which communications are either scheduled using task-level offsets, job-level offsets, FIFO or EDF. Data is transferred in chunks of 32 bits. Once a memory transfer is started, it cannot be preempted and it is achieved to completion. Memory phases are triggered using a single STM-timer managed by the core of index 5. In our software architecture, this core has been reserved to manage the scheduling within the platform by using a timer interrupt. When the timer fires, the memory phases activation handler is invoked to manage the memory phases, according to one of two cases: (i) Time-triggered scheduling (task-level or joblevel offsets): the memory transfer is immediately triggered on the DMA; (ii) FIFO/EDF: the timer fires at each task period. According to the memory scheduling policy, the scheduler inserts the memory phase into a priority queue ordered by FIFO or deadlines. The highest priority memory phase in the queue is triggered on the DMA. Then, the timer is configured for the next memory phase activation. At the completion of every memory phase, the scheduling manager implemented on core 5 inserts the computation phase into the priority queue of the core where the task is allocated and sends an intercore interrupt. The core scheduler then executes the highest priority active tasks in its run-queue, according to its scheduling policy.

To study the performances of the proposed approaches, we first measured the data-transfer time and execution times of several tasks from different benchmarks, with different input data size: from MIbench , FFTbench and Mälardalen . The task code (not the functional part) has been modified : first a memory phase is performed to transfer data from/to the local scratchpads, then the task code is executed on the local memory. We slightly modified the different benchmarks to fit with our hardware limitation, e.g. using 16 bits integers rather than 32 bits integers, etc. The considered tasks are : qsort, susan (edge-detection-L), FFT (Fourrier Transofrmation), MATMUL (Matrix Multiplication), FIR (FIR filter). All FIR task versions (with different size of input have a high stall (12%-15%). All the other tasks have a small stall (≤ 8%).

We select for every scenario a subset of tasks from our benchmark, and we follow the same techniques to generate our periods and deadlines as those of Section VI-A. We assign offsets and deadlines by running our methods on the obtained task set. Experimentally, we did not find any task set schedulable with WF-FP and that is not by our methods, therefore, if the task set is not schedulable by our method, we drop it. Otherwise, we execute the task set on the Aurix platform. We do not run schedulability analysis for [START_REF] Arora | Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF], as it does not propose technique to improve predictability of PREM tasks but just analysis of existing designs. In Table I, we report the performances in terms of deadline miss rate.

Every row in Table I corresponds to a different scenario: we varied the total utilization and tasks profiles.The total utilization is derived using estimated benchmarks prefetching and computation times. In the column stall, we report the category of memory stall for the scenario: when it is set to L, the task set is composed of tasks in majority having low stall (≤ 0.05); when it is set to H, the task set is composed in the majority of tasks having high stall (≥ 0.1); when it is set to L/H, the task set is a mix of both. In each column, we report the number of deadline misses divided by the total number of jobs for each different method. Every experiment has been run for 10 seconds. Untested scenarios are due to the high complexity of ILP-based approach.

As you can notice, the approach of [START_REF] Arora | Bus-contention aware schedulability analysis for the 3-phase task model with partitioned scheduling[END_REF] is very sensitive to the memory stall. When stall is low, the task set misses fewer deadlines compared to large stalls. Indeed, the high priority computation phases might suffer from long blocking times due to the FIFO scheduler on the bus. While it is well known that FP scheduling does not suffer from the domino effect, when using FIFO on the bus an indirect domino effect might appear as computation phase does not become ready before the completion of memory phase. In the other hand, our methods (both the task-level offset method and the intermediate deadlines method) perform much better: their behavior adapts to memory phases length as the latter are coscheduled according to their urgency, computed based on the cores schedulability. As the load increases even our methods present a percentage of deadline misses. These are due to the unsafe WCETs used in the analysis, and could be avoided by using a proper WCET analysis tool. Please also notice that our methods recover faster than WF-FP, as the main problem is the bus congestion which is completely avoided by our methods.

VIII. CONCLUSION AND FUTURE WORK

For a COTS platform comprising multiple CPU cores, contention for memory accesses can cause a significant decrease of schedulability. In this paper, we proposed several techniques for contention avoidance. Our experiments show a significant improvement in the system performances compared to stateof-the-art. We demonstrate the applicability of our techniques with an implementation on a real hardware platform and on realistic benchmarks. As future work, we plan to extend our techniques to AER task model, DAG tasks, and to take into account allocation strategies in the analysis phase.

Fig. 1 :

 1 Fig. 1: Multicore target platform.

Fig. 2 :

 2 Fig. 2: Example of task parameters.

2 {Computes the intermediate deadlines} 7 :

 27 add (M i , δ i ) to S

  ∀τ i ∈ UnSchedulable : ub i ← δ i

Fig. 3 :

 3 Fig. 3: Schedulability of ILP vs heuristics approaches

Fig. 4 :

 4 Fig. 4: Heuristics algorithms performances

TABLE I :

 I Execution on the Aurix platform: # deadlines misses


Reporting Context Aware Partial Translation engine based on immediate and delayed Rule application

Keywords: Migration, Iterative, Incremental, Context-Aware, Microservice, Monolith, Standalone, Software Evolution, Refactor Public Function testLen() : Void Call Assert(Len(HelloString), 5, "Should be 5") End Function

Language migration has been the driver of many efforts resulting in multiple solutions and strategies.

One of the most popular approaches for dealing with it is source code translation: it proposes to translate the source code of an application to a target language. For doing so it leverages a set of translation rules based on the grammatical constructions provided by the source and target languages.

However, we notice that even when most of the literature acknowledges translating implies migrating the runtime, libraries and the Software Development Kit (SDK), none of them proposes a systematic way to solve this problem. Along with this, we notice that there are many proposals to shift the paradigm from procedural to object-oriented programming based on how to propose classes automatically. But we found nothing on how to translate the expressions that use functions into expressions that use methods. In the context of migration from Microsoft Access (MS Access ) to web technologies, these two lacks threaten seriously any attempt to produce even a compilable version of the code on the target technology.

This article proposes a translation engine that split the translation process into two phases. A phase of language translation, and a phase of adaptation to the target environment. The first phase is in charge of producing declarations, and the second one is in charge of adapting the usage of this declaration to fit the translated version of our artefacts.

We argue that enabling to adapt the code to fit the translated version of our artefacts allows the definition of simple adapting rules able to deal with a large share of both problems: (i) runtime, libraries and the Software Development Kit (SDK), and (ii) simple paradigm shift.

This article presents some basic adapting rules and validates our approach by translating a battery of simple tests that feature the usage of a carefully chosen set of features.

I. INTRODUCTION

During language migration, we are required to change the language of a program: to express the source program semantics in a new language.

Language migration is a deceiving task. It seems to be as simple as translating language constructs (something that can be already complex by itself). Even considering languages that have similar grammatical constructions, languages often run on different environments with different SDK and libraries available and, never the less, different best practices, which leads to substantially different ways to define APIs, and compose and reuse code.

After translating a project from one language to another with the purpose of migration, we expect to have the same behaviour and to use the target environment: runtime, SDK, libraries: all that makes this environment a desirable target.

We find out that even when syntax-based translation is implemented with AST rewriting is a powerful tool, it is hard to define rules that apply to all usages of a specific artefact, to replace one library with another or even one piece of our code with some library usage from the target environment.

In this article, we explore the possibility of a language migration based on language constructs and language semantics. This article continues as follows: Section II specify in detail what has been done, and why is not enough for our case of study. Section III presents the research questions that will guide our research. Section IV explains the importance of reifying the relation between declarations and usages and proposes a variation of the Abstract Semantic Graph. Section V proposes a translation engine able to apply translating and adapting rules. Section VI analyzes the potential of the adapting rules for migrating runtime, paradigm and libraries. Section VII proposes and conducts a validation that involves the translation of programs from MS Access to Java and Pharo Section VIII discusses the threats to the validity of the conducted validation. Section IX concludes and proposes future works on the subject.

II. TRANSLATING SOURCE CODE

In the context of a collaboration with Berger-Levrault, a major IT company, we are working on the migration of MS Access monolithic applications to web Typescript/Angular front-end and Java/Springboot microservices back-end. The minimum requirement of our software migration is to translate MS Access 's flavour of Visual Basic for Applications (VBA) to Java and Typescript, ensuring that the code uses their respective runtimes, SDK, libraries, frameworks and paradigm.

A. Source code Translation

Language translation has been addressed as a compiling problem [START_REF] Alfred | Compilers: Principles, Techniques and Tools[END_REF][START_REF] Alfred | The Theory of Parsing, Translation and Compiling Volume I: Parsing[END_REF][START_REF] Andrew | Modern compiler implementation in Java[END_REF]. Software migration is not compiling but many techniques used in compiling can be leveraged in our favour. This has been done in the past for conducting successfully language migrations [START_REF] John | Extreme Maintenance: Transforming Delphi into C# // ICSM'10[END_REF][START_REF] Kontogiannis | Code Migration through Transformations: An Experience Report[END_REF].

However, translating is more than changing the language. To change runtime and libraries is imposed (except in rare occasions [START_REF] Bruno Góis | Learning migration models for supporting incremental language migrations of software applications[END_REF]). Terekhov, Verhoef [START_REF] Terekhov | The realities of language conversions[END_REF] points explicitly out how this problem has been neglected. Despite all these notices and recognition, it has not been dealt with systematically.

B. The problem

Lets consider the code in Listing 1. A Visual Basic Application module used for testing named Testing, with a function testing the function Len using HelloString global variable as a parameter. This global is defined in another module named ProjectGlobals.

Listing 1: Testing the function Len

If we use a translation approach with Java and JUnit 3 as a target in mind, we could quickly propose some rules of translation:

1 Translate the module as a class subclass of TestCase. 6 Translate the call to Len(x) as x.length().

If we define such rules in a translation engine such as the one used by Brant et al. [START_REF] John | Extreme Maintenance: Transforming Delphi into C# // ICSM'10[END_REF] 1 we will be able to translate this method into Java. However, there are three main restrictions in this approach: By having rules that express how to write expressions such as [ParentName].[GlobalName], we make an assumption that impose strict constraints over what, how and in what order something is going to be translated.

a) The importance of what, how and when to translate something: What to translate is never a clear decision. Much of our code may have no sense of the target or being replaced by a target library, a service, etc. Are we sure that we want to translate ProjectGlobals? Are we sure we want to translate the global HelloString? If we decide to not translate the module ProjectGlobals we will be forced to review or create new rules to contemplate this exception. How to translate something is not an easy decision either. Is HelloString going to be translated as a static public variable? Without any accessor? If we decide finally to translate HelloString as an accessor getHelloString() we will be forced to review or create new rules to contemplate this exception. The Order of translation is even more complex. We could propose to translate things in order of dependency, which would solve many technical problems, but are we going to translate the full module ProjectGlobals to be able to translate our test? To our client's needs, this order may be a waste of time.

b) The importance of being agile: We argue that a translation is too complex and too risky to not be agile. We want to be able to do partial translations in order to do the minimum for being able to make one thing work at a time. We argue that changing our minds should be relatively easy and affordable.

1) Library migration: It is an area of study on its own. Even updating a library, or migrating from one version to a newer one, can be already challenging. Cossette, Walker [START_REF] Bradley | Seeking the Ground Truth: A Retroactive Study on the Evolution and Migration of Software Libraries[END_REF] explains very carefully the problem of library migration, and it proposes to group API transformations, according to the degree to which they believe that they can automatically be enacted. Here we recover the part that applies to our study case.

• Fully automatable transformations involve API changes that do not alter the semantics of the API significantly.

i.e., function rename, remove a parameter, reorganize parameters. • Hard-to-automate transformations are cases that represent significant alterations to the semantics of entities between libraries; a tool is unlikely to handle such a transformation without assistance from a developer. i.e., Add parameters, Feature deletion (the feature does not exist on the target), API replacement. This work is mainly inspired by [START_REF] Stéphane | Deprewriter: On the fly rewriting method deprecations // JOT[END_REF] 2) The paradigm migration: Paradigm migration or Paradigm shift is also a subject that had a lot of attention. It is noted that we choose to take the easy way out of it, by using static "class methods" on all our destinations. This reduces drastically the complexity of our problem, but we still must deal with the problem of changing the way we use this code to be adapted to the object-oriented paradigm. For example, all the function calls must be transformed into method invocation, which implies inferring which object or class the receiver has to resolve this method.

3) Sumary: Language translation rules must assume some knowledge of the language. Naive approaches to assumptions can lead to wrong translations. Both facts threaten the reusability and validity of rules. Library and paradigm migration have one thing in common: both affect what is available to use, and how to use it.

III. RESEARCH QUESTIONS

We consider that most of programming languages respond to three different kinds of constructs: Declarations, Statements and Expressions. Declarations are the definition of structural and identifiable artefacts of some specific nature: types, functions, etc. Statements are syntactic entities defining actions to be carried out. Expressions are also actions to be carried out, but an expression also yields a value.

Declarations are to some degree, always defined in terms of other declarations. Either declared in the language or provided by the runtime like primitives. e.g., Classes are declared referring to their superclasses. Behaviour is also defined in terms of other declarations. e.g., Functions behaviour is based on applying other functions by referring them through function invocations. We call those elements used to relate an entity with a declaration Reference, or referential code. There is an implicit dependency between the nature of a declared artefact and the kind of reference able to interpellate it. If we use a function invocation (kind of reference) to execute a behaviour, therefore, the declared artefact is a function. If an artefact is declared as a function with one parameter, to be used for execution, it must be through a function invocation with one argument.

In this article we support the following claims: (i) given the reference of the source program, and the declaration that it is expected to refer in the target program, we can automatically propose a pertinent translated reference: including adapting different references to use pre-existing artefacts (SDK, Libraries, Types, etc) in the target system, and to adapt to the target system paradigm. i.e., if we know that the reference is a function invocation and that the target is a static method, we can automatically write a static method invocation as translation. By doing so, we reduce the impact of decisions like what and how to translate an artefact. (ii) to delay the translation of a reference to the moment when the engine finds evidence of what the expected declaration to be referred to reduce the impact of the translation's order.

From these claims stem the following questions: RQ#1 Can we delay the translation of a reference to the moment when the referee is defined? RQ#2 Can a delayed translation rule transform a reference to use the target environment's pre-existing artefacts (SDK, Libraries, Types, etc)? RQ#3 Can a delayed translation rule transform a reference to use the target environment's paradigm? IV. REPRESENTING THE REFERENCE -DECLARATION BINDING WITH AN ABSTRACT SEMANTIC GRAPH a) Abstract Semantic Graph: Our proposal is based on a common program representation model. For doing so we use a representation popular in the domain of program transformation named Abstract Semantic Graph (ASG). An ASG is a graph that extends the Abstract Syntax Tree (AST) structure by linking artefact uses to its definition through symbol resolution. In our version, the link between any entity and a Declaration is reified as a Reference object. A function declaration uses a TypeReference object for referring to it's returning type. A function or method invocation is considered to be a reference as well.

Figure 1 is a graphical representation of a ASG instance which represents the source code listed in Listing 1. Reference objects are denoted with double strokes. The dotted line represents the relation between a kind of reference object and a declaration. Like this, the function declaration node has an arrow pointing to a type-reference object, which has a dotted line arrow pointing to the type Void. We note that our ASG reifies and uses polymorphically runtime, library and userdefined artefacts. From our object model point of view, the difference between them is their tag. It is to note that a library function keeps its parameters but has no body.

b) Heterogeneous Abstract Semantic Graph: We call our ASG heterogeneous because we use it to represent many languages. Different concepts are modelled by different classes. When representing a new language the rationale is the follow-ing: if we need to represent a concept that we already used and from the point of view of migration is equivalent (an expertise task that we are not going to discuss in this article), we reuse the same class. This is for example the case of the classes representing the If, While and For statements. If we do not find an equivalent, we add a new class. We always try to reuse what is possible but to avoid compromising its unique semantic value. This is why we have ClassWithNamespace to represent classes that like in Java can declare inner classes, DecoratableClass to represent classes that like in TypeScript can be decorated.

V. RQ#1: CAN WE DELAY THE TRANSLATION OF A REFERENCE TO THE MOMENT WHEN THE REFEREE IS DEFINED?

To respond to this question we have to start with a quick proposal for a translation engine. The translation engine receives a source unit of code to be translated and the target where to aim to translate. By translation, we mean the same kind of syntactic tree transformation proposed by [START_REF] John | Extreme Maintenance: Transforming Delphi into C# // ICSM'10[END_REF][START_REF] Kontogiannis | Code Migration through Transformations: An Experience Report[END_REF] A. General Approach 1) Load source project: The engine loads an ASG for the source project. Source entities are the units to be translated. MS Access offers many kinds, in this article, we focus exclusively on Modules and Classes. This ASG includes all the Modules and Classes defined by the users and those specified in runtime, libraries and SDK.

2) Load target project: We argue that no translation project starts from thin air. There is always an idea of architecture and what libraries we aim to use. The target model allows us to: (i) know what are the available libraries on the target e.g., we may want to use specific third-party libraries. (ii) to aim where to translate something e.g., a previously existing package, or a previously existing class.

The engine loads an ASG for the target project. This ASG includes all the artefacts defined by the users and those specified in runtime, libraries and SDK.

3) Configuring rules: Each translation requires different rules that are suitable for translating different languages. We model rules as objects to be able to easily add them to the engine according to the desired behaviour. Rules are discussed below in Section V-B 4) Mapping: Once we have entities from source and target projects we can establish semantic equivalences. We have two kinds of mappings: (i) Simple mappings that allow telling that a source entity is equivalent to a target entity. We use this mapping to relate types e.g., the typed string from MS Access is mapped to the String class defined in the java.lang library. (ii) Nested mappings that allow telling that a source entity is equivalent to a target entity and that the direct children must be mapped as well e.g., a source function may be mapped to a method, where the first argument is mapped to be the receiver of the method invocation and the rest of the arguments are kept in the same order. The user is expected to map all the possible entities before continuing to the next step.

5) Translation:

The engine is given a set of source entities to translate and a target which to translate. e.g., some MS Access modules as source entities, a Java package as a target. The engine applies different rules over the different source entities to produce the translated code within the given target. e.g., to translate the MS Access modules as Java classes in the given package.

B. Rules

Rules are conditional operations, that applied over an accepted entity and return a new entity. We consider a rule to be an instance of a class that responds to two methods, a conditioning method and an operation method. Condition consists of a predicate that allows the user to define specific requirements for the operation to be applied. Operation consists of any systematic modification over the target. A rule returns a single entity.

Each time the engine creates a target entity with a rule, it traces down the relation: the target entity T was produced by applying the rule R to the source entity S. Each time the engine creates a target declaration out of source declaration it produces a simple mapping between these artefacts to establish a semantic equivalence, as explained in Section V-A4.

C. Translating phase 2 The engine traverses hierarchically the source entity avoiding the links between reference and declaration objects. For each source entity, it applies a "translating rule" to produce a target entity. Each produced target declaration based on a source declaration is mapped as a simple mapping. We call this first part Translating phase.

1) Translating rules: Rules to be applied during Translating phase. They represent the production of a target entity based on a source entity.

a) Copy translation rule: Listing 2 lists the copy rule. The first method represents the condition. It is parametrized with the source entity, the target context entity (where the target entity is to be written) and the writer to be used. In this case, it yields always true. The second method represents the operation. It is parametrized with the source entity, a targeted writer and the engine (for it may need to delegate to other rules). In this case, it attempts the copy the source entity into the target entity.

CopyRule>>matches: aSourceEntity context: aTargetContextEntity with: aTargetWriter ˆtrue CopyRule>>applyTo: aSourceEntity destinationWriter: aTargetWriter engine: anEngine ˆCopyHelper copy: aSourceEntity into: aTargetWriter

Listing 2: The copy translation rule is an attempt of copying the source entity into the target This rule is permissive, and it could end up producing function invocations in a java method, the thing that we know is wrong, but the copy can be rewriten later by an adapting rule. b) Syntactic mapping example: Listing 3 lists and example which transforms a function or sub-procedure into a static method. Listing 3: Syntactic mapping transformation example. Transforming a function or sub-procedure into a static method

The condition ensures that the source entity is a function or a sub-procedure. It also ensures that we are going to be writing inside a class. The operation writes a method: (i) it copies the selector, (ii) if it is a sub-procedure sets void as return type, (iii) sets the method as static (iv) delegates to the engine the migration of all the children.

Other declaration-related rules have similar implementations such as ModuleToClass or VariableToProperty.

c) Translating example: Let's consider the translation of the ASG proposed in Listing 1. From MS Access to Java. We will leverage the following rules: ModuleToClass, FunctionToMethod and Copy.

The outcome is shown in Figure 2.

We note that the invocations to Len and Assert functions in our result are wrong, but we leave it there to be adapted when there is an equivalent entity in the target.

2) Installing linked stubs: Up to this point, we can translate code eagerly by applying Translating rules. The translating phase finishes by marking all the references that have been created to be taken into account in the adapting phase. To mark these references we are going to set as referee a "linked stub".

This linked stub will hold a reference to the source reference's referee that produced the target reference i.e., the buggy function call to Assert in our target will have as a referee a stub that links to the Assert function defined in the source model. This stub has two responsibilities (i) mark a reference to be processed (ii) trace fine-grained relations.

In order to build this stub we need to have an engine that keeps the traces between source and target entities. The thing that our engine does as explained before in Section V-B.

D. Adapting phase

The engine follows up with the Adapting phase. The engine iterates all the reference entities that were marked with linked stubs, as explained in Section V-C2. For each entity, it applies an "adapting rule" to ensure that the reference object is fit and able to refer to a target declaration. Parametrized with the target reference, the declaration held by the linked stub, and the available mappings so far. It yields true if: (i) there is an equivalent declaration in the target model. (ii) it can be referred by tgtReference (if it is a type-reference and the mapped declaration is a type this is true). (iii) no arguments are given to the reference and no parameters are required for the declaration. The condition ensures that the only real thing that could change is the name. Nothing else would matter. And that is what the operation does: it sets the referee to the mapped declaration and it sets the name, to ensure that the reference complies with the use of the same name as the declaration. E. Summary: Can we delay the translation of a reference to the moment when the referee is defined?

In this section, we proposed a method able to delay the application of rules to the moment when a mapping is possible. We content ourselves by knowing that there is at least one way, and it responds to the requirements.

VI. RQ#2 & RQ#3: CAN A DELAYED TRANSLATION RULE TRANSFORM A REFERENCE TO USE THE TARGET ENVIRONMENT'S ARTEFACTS & PARADIGM?

We remember that the engine gathers all the mapping information, either produced by the user during engine configuration as explained in Section V-A4, or produced by the translating phase as explained in Section V-C.

In this section, we respond to these questions by proposing five rules that will be verified (i) Simple rename, (ii) Rename Map arguments with static receiver, (iii) Rename Map arguments with this receiver, (iv) Rename Map arguments with argument receiver, (v) Autowrap missing library.

A. Simple and Nested mappings

Before stepping further into the definition of the adapting rules, we want to be crystal clear on what our mappings are.

a) Simple mapping: A simple mapping is an object that relates a source declaration with a target declaration. It works as a simple association and it implies that it implies that the source declaration is equivalent to the target declaration in the target ASG. This mapping is enough to map two entities without parameters, or two target entity that was produced based on the source entity (assuming that if there are parameters, they did not change order). e.g., (Void => void); (String => String); etc. b) Nested mapping: As a simple mapping, it associates a source declaration with a target declaration. It does as well map all the parameters between source and target declarations. This mapping allows also to specify if a parameter on the source declaration becomes a receiver in the target. e.g., let's consider the mapping between function F(x,y,z) and method M(a,b,c). Three mappings examples could be:

• (F => M (a => z; b => y; c => x)): all the target parameters are mapped to all source parameters. The order changes. • (F => M (a => x; b => y; c => x)): parameters a and c are mapped to x; parameter b is mapped to a. Parameter z is dismissed. • (F => M (a => x; b => y; c => x; z => R)): parameters a and c are mapped to x; parameter b is mapped to a. Parameter z is proposed as receiver. c) Mappings are only evidence: The proposed mappings do not offer any behaviour. There are there to log of "evidence" of the relation between two artefacts. A mapping can be the outcome of the user manually configuring the engine as explained in Section V-A4. It can also be the outcome of the engine establishing a relationship between two entities as explained in Section V-C. The mappings are maintained in a list to be queried by the adapting rules when being applied.

B. Simple rename: Renaming types and simple invocations automatically

Condition 1) There is a target declaration mapped AND

2) The target reference can refer to the target declaration (e.g., A function invocation cannot refer to a method) AND a) Mapped source and target declarations have no parameters OR b) All the source parameters are optional AND

The target reference has no arguments. Operation 1) Ensure that the target reference uses as identifier the same identifier as the target declaration. 2) Ensure that the target reference refers to the target declaration. This rule describes a version a bit more complicated than the one presented before by Listing 4. This version ensures that there are no parameters on the declaration. It contemplates the possibility of the source declaration being addressed with no arguments.

For example, the declaration of the variable name uses a type reference that refers to the primitive type string. We map the MS Access type string with the Java class String. The engine would execute this rule: (i) The type reference target is allowed to point to the String class. (ii) The type reference has no parameters, therefore all the conditions are met. The operation will check that the literal hold by the target reference is string instead of String (mind the uppercase), and therefore modify the type reference to fit in.

C. Rename & Map arguments with static receiver

Condition 1) There is a target declaration mapped AND 2) The target reference cannot refer to the mapped target declaration AND 3) The mapped target declaration is a method or an attribute AND 4) The mapped target declaration is static. Operation 1) If the mapped target declaration is an attribute, write an attribute access expression (which is a reference) using the parent of the attribute as a receiver. 2) If the mapped target declaration is a method, write a method invocation expression (which is a reference) using the parent of the method as a receiver. 3) Set the arguments in the new target reference according to the mapping information. 4) Set the new target reference to refer to the mapped target declaration. For example, invocation of the function Date (which yields the date of today). We map the function Date with the static method LocalDate.now. After copying the usage of this function as function invocation in java, the engine would execute this rule: (i) there is a target declaration mapped: LocalDate.now. (ii) The function invocation cannot refer to it: is a method. (iii) LocalDate.now is static. With all the conditions met: the operation would yield a new expression that will replace the old one. This expression would be a method invocation "LocalDate.now()"

D. Rename & Map arguments with self receiver

Condition 1) There is a target declaration mapped AND 2) The target reference cannot refer to the mapped target declaration AND 3) The mapped target declaration is a method or an attribute AND 4) The target reference is used in the context of a method AND 5) The mapped target declaration is reachable from the calling context by using self or super. Operation 1) If the mapped target declaration is an attribute, write an attribute access expression (which is a reference) using super or self as receiver. 2) If the mapped target declaration is a method, write a method invocation expression (which is a reference) using super or self as receiver. 3) Set the arguments in the new target reference according to the mapping information. 4) Set the new target reference to refer to the mapped target declaration. For example, invocation of the function Assert as used in the example. We map the function Assert with the method Asserter.assertEquals. After copying the usage of this function as function invocation in java, inside a method of a subclass of TestCase (JUnit3). the engine would execute this rule: (i) there is target declaration mapped: Asserter.assertEquals. (ii) The function invocation cannot refer to it: is a method. (iii) Asserter.assertEquals is reachable by using self. With all the conditions met: the operation would yield a new expression that will replace the old one. This expression would be a method invocation "this.assertEquals(...)"

E. Rename & Map arguments with argument receiver

Condition 1) There is a target declaration mapped AND 2) The target reference cannot refer to the mapped target declaration AND 3) The mapped target declaration is a method or an attribute AND 4) The mapping offers a parameter as a receiver. AND 5) The type of receiver can reach the target declaration mapped. Operation 1) If the mapped target declaration is an attribute, write an attribute access expression (which is a reference) using the argument that responds to the mapping as a receiver. 2) If the mapped target declaration is a method, write a method invocation expression (which is a reference) using the argument that responds to the mapping as a receiver. 3) Set the arguments in the new target reference according to the mapping information. 4) Set the new target reference to refer to the mapped target declaration. For example, invocation of the function Len as used in the example. We map the function Len with the method from String.length, to be resolved by the argument.

After copying the usage of this function as function invocation in java, with a string as an argument. the engine would execute this rule: (i) there is target declaration mapped: String.length. (ii) The function invocation cannot refer to it: is a method. (iii) String.length is reachable by using the argument. With all the conditions met: the operation would yield a new expression that will replace the old one. This expression would be a method invocation "argument.length()"

F. Autowrap

3 Defines a new declaration that wraps a call to the target declaration respecting the source declaration order of parameters.

Condition 1) There is no target declaration mapped AND 2) The source declaration was defined in a library AND It is not a type. Operation 1) Automatically translates the library component into a pre-established destination. If a piece of code uses a library artifact that we cannot map, we have two options: (i) dismiss the code,(ii) migrate the library manually. If we dismiss the code we would not be translating this piece of code. We consider then that the only alternative is to migrate manually the library. For easing the job, we propose to generate automatically an equivalent structure to let the user to define the behaviour. b) Rename & Map . . . with . . . receiver: All of them address the problem of transforming a function or variable access into a method or attribute. All of them apply a rename if required, and all of them are able to shuffle parameters order based on the mapping configuration. All of them promote an object as receiver. The static rule promotes the defining class. The self rule promotes self or super. The argument rule promotes one of the arguments. c) Autowrap: produces a skeleton that responds to the used artefact, leaving the developer to fill-up the blanks.

VII. VALIDATING THE RULES

As we said before our project stems from a collaboration with Berger-Levrault, a major IT company. Therefore our validation is concerning one of the running migration projects. For validating our approach we did as follow 1) Created a library testing project based on the analysis of an industrial project. 2) We mapped our engine for Java and Pharo languages.

3) We translated the tests on both destinations. 4) We measured by the following criteria

• Is the resulting test Parsable?

• Is the resulting test Compilable?

• Is the resulting test Red, Yellow (or Blue) or Green?

A. Crafting a representative source project

There are many reasons to not use an industrial project as a source for validation. Firstly, the language translation is a big part of our industrial migration, but it is not all. The details required to grasp the overwhelming complexity of the problem cannot fit into half a page in a validation. Second, it will be an undisclosable source of proprietary code, which would make the example less than interesting.

We propose then to make up our source project. But to make it an interesting case of study we require two things: (i) it must respond to the library and runtime usage of a real project. (ii) it must be testable.

1) Choose the library elements: None of the projects we have to migrate uses everything from every library. To validate our approach we address one of our migration projects.

a) Demographics: The chosen project is Microsoft Access project that consists of 18 subprojects, summing up 1000 UI widgets and 700k lines of code and using 19 different libraries. This project uses almost 690 different elements from different libraries.

b) First filtering: We use the analysis tool proposed by Bragagnolo et al. [START_REF] Santiago | Alce: Predicting Software Migration[END_REF] to select the most meaning full by applying the Pareto principle (also known as the 80%-20% rule). That yielded a list of 160 elements that represent 80% of library usage in the project. This list is available in validationresults.xls. c) Second filtering: From the yielded list, we filtered out all the elements regarding MS Access infrastructure, UI, file system or those which cannot be unit-tested.

MS Access infrastructure provides many helping elements unconceivable on the target. For example the"CurrentDB" global. Our language translation project does not consider UI (which will be migrated differently). Our target is either a back-end or a front-end program. While in MS Access makes sense to access the user's files, it is not the same for either back-end or front-end applications. Therefore all the code using those functions must be rewritten. Finally, the ADODB and DAO objects (Recordset, Database and Connection classes), cannot be unit-tested. We originally did the test and try to add it to the validation, but it cannot be unified, since a single testing method over the database requires to have some setup and cleanup. This list is available in validation-results.xls.

2) Writing tests: We implemented an extremely humble testing library in MS Access . Each test is a function. We have no setUp. We have a single implementation of Assert which receives two entities to compare for equality and a text to show if the assertion fails.

We created four different modules according to the kind of tested entity: types, functions/subprocedures, constants/globals and methods.

Testing

Public Function testUCase()

Call Assert(UCase("hellow"), "HELLOW", "Upper case expected") End Function Listing 7: Upper case must be upper.

3) The source project: The source application is available PaperTest.accdb.

The source project we propose for the validation consists of 55 tests split in four different modules. 14 tests of constants and globals, 18 tests of types, 21 tests of functions.

B. Getting to know our targets

The target applications are available in the target folder. Our validation translates 53 tests, which were detailed in Section VII-A, to two different targets. Here we briefly describe what we find in these two target projects.

1) Common decisions: This validation is not about migrating tests to be used by a Test framework, since we have found none in MS Access and there is no usage of something similar in our industrial projects. Therefore, to simplify and avoid polluting the engine configuration, we expect the target projects to have four different testing classes to receive the translation of the tests of each of our four MS Access testing modules.

2) The Java target: Java is a popular statically typed objectoriented language. The target is a Maven project configured to compile Java 1.8 and with a single dependency: JUnit3. This dependency is required to support testing. The rest of the available dependencies are the many definitions available in the JDK. As previously existing code, to simplify the experiment, we defined four empty test case classes using the Eclipse default template. These classes are a subclass of the junit.framework.TestCase class. We find also a class named Example. This class exists because of a technological restriction of our Java ASG loading module: it only loads used pieces of the libraries. This class is not used at any moment.

3) The Pharo target: Pharo is a popular open-source dynamically typed pure object-oriented language, inspired in Smalltalk. The target is a Pharo package that includes the four expected TestCase classes developed in Pharo 10. Pharo ships many dependencies within the Pharo image, including from the definition of Object and SmallInteger to the SUnit testing framework. During our Pharo ASG loading process we cut down the available dependencies to ensure that we do not load useless stuff. For this experiment we cut down the dependencies to the following packages: 'Kernel-BasicObjects', 'Kernel-Objects', 'Kernel-Numbers', 'Kernel-Chronology', 'Kernel-Exceptions', 'Collections-Abstract', 'Collections-Sequenceable', 'Collections-Unordered', 'Collections-Strings', 'SUnit-Core'.

C. Rules and Mappings

1) Installed Rules: For both engines, we used the same kind of translation and adapting rules. We use the following five translating rules: ModuleToClass, FunctionToMethod, Copy, (three of them discussed in Section V-C1) and GlobalToAttribute, which transforms all global variables or constants into a static attribute. We need an extra rule to transform three different binary operations according to the target language.

CopyReplaceBinaryOperator, which copies a BinaryOperator structure replacing the operator. There are two ways to express equality in MS Access : A Is B and A = B. Both are translated as A == B in Java and as A = B in Pharo. There is also the concatenation in MS Access : A & B. Translated as A + B in Java, and A , B in Pharo. We want to note that this set of rules is not enough to translate a full MS Access program since control flow statements are not taken into account in our experiment, since they are out of scope. For the adapting rules, we use the five rules discussed in Section VI.

2) Mappings: From the mappings point of view, we configure the engine according to the target ASG. Table I show some elements that we mapped in one language and not in the other. The full list can be found in validation-results.xls.

D. Results

The translating application ready to reproduce the experiment is available in Application.zip. We want to insist on the fact that the engine was configured with the same set of translation rules (with a slightly different configuration), and with the same set of adapting rules to produce two different OOP targets, with different types of typing systems and libraries. The main difference between the configurations was the source and target ASG mappings.

a) Mapping Parsing and compiling: Figure 3 shows how many entities were successfully mapped, how many translated tests were successfully parsed, and how many of them were correctly compiled. For Java, we mapped 47% of entities. 58% of them in Pharo. For both targets, the produced source code is verified by the SmaCC Java4 parser and the Pharo parser. 47% of the translated testing methods are compiled by the Java compiler. 100% are compiled by the Pharo compiler. The compiling rate seems to be tightly related to the mapping in the case of Java since the compiling errors come from wrong typing. We argue that most of them stem from the MS Access type named Variant, which we mapped to Object in Java. MS Access Variant accepts any value but keeps the type of the element (object or not). In Java, the type Object accepts only objects (no primitive values allowed) but if a variable is typed as Object it loses all singularity. b) Tests: Figure 4 shows in a stacked bar plot the amount of executed tests split by the result: success, failure and error, and at the same time, it split the errors and failures by kind. All the successes make sense, so we do not classify them. We have three kinds of failures: Only in Java do we find failures because of the wrong literal translation. i.e., testing if a double variable value is 0, it must be used 0d. Only in Pharo do we find failures related to untyped variables. In Pharo, all the variables start with nil because all possible value is an objects. In both targets, we find failures due to bad mapping. Some functions seem to do the same this is not exactly true. Str(3) is expected to return " 3" note the whitespace. We found no method doing the same in Java or Pharo. We have three kinds of errors: On both targets, we find errors due to the usage of the Autowrap rule. These errors a fully expected, since the rule generates methods that raise exceptions asking the developer to implement the behaviour. On both targets, we find errors due to wrong mapping. i.e., MS Access allows using strings indicating time to create a Date. Finally, only in Pharo do we find errors because the job of the Autowrap rule was not enough: In Pharo, all the attributes of an object or class are only accessible by the class itself or by subclasses. Meaning that when the Autrowrap rule creates equivalent globals (as class side "static" attributes) we must also implement the accessors. And all the accesses to attributes must be rewritten as accessor invocation.

VIII. THREATS TO VALIDITY

There are two main threats to the validation proposed.

a) Tests cases coverage: The written tests are based on simple usage of functions. We did not investigate in depth to understand the limit of validity of the MS Access functions in order to test not only a simple case but also the limit cases.

b) Tests simplicity: The second threat is that the validation is done over a set of simple tests. We focused strictly on Reference objects, what took out of the equation another kind of construction such as control flow, and the analysis of how control flow translation rules work together with adaption rules.

IX. FUTURE WORK AND CONCLUSION

The main hypothesis of this article is that we can adapt code based on the nature of the artefact. .......

Fig. 1 :

 1 Fig. 1: ASG Object Model. Reference objects are denoted with double strokes.

1 )

 1 Fig. 2: Translation

  SimpleRenameRule>> matches: tgtReference toAdaptAs: srcDeclaration mappings: mappings selectedMapping := mappings detect: [: map | (map source = srcDeclaration) and: [ (tgtReference refersToObjectsLike: map target) and: [ tgtReference hasNoArguments and: [ map target hasNoParameters ] ]] ] ifNone: [ nil ] . ˆselectedMapping isNotNil SimpleRenameRule>> adapt: tgtReference toFitTheEquivalentTo: srcDeclaration writer: aWriter using: aFylgja tgtReference name: selectedMapping name. tgtReference referee: selectedMapping target ˆtgtReference Listing 4: Rename adapting rule Adapting rules examples are introduced and carefully anal-ysed in Section VI.

G

  . Summary: Can a delayed translation rule transform a reference to use the target environment's artefacts & paradigm? a) Simple rename: renames what ever element that is paradigmatically equivalent, and semantically chosen as equivalent by the mappings of the user.

Fig. 3 :

 3 Fig. 3: Bar chart comparing the number of mappings and the impact on parsing and compiling.

Fig. 4 :

 4 Fig. 4: Stacked bar chart comparing tests results per language

  types: The test asserts the default value of a declared variable. Example given in Listing 5. The test that asserts the default value. Example given in Listing 6.

	Public Function test_ErrObject()
	Dim var As ErrObject
	Call Assert(var Is None, True, "None expected")
	End Function
	Listing 5: Default value is None.
	Testing Constants: Public Function testVbNullString()
	Call Assert(vbNullString, "", "Constant Expected")
	End Function
	Listing 6: Null string is an empty string.
	Testing Functions: The test asserts examples of usage.
	Example given in Listing 7.

TABLE I :

 I Mapping examples:

	VBA	Java	Pharo
	Information.TypeName None	Object.className
	Interaction.IIf	None	Boolean.ifTrue:ifFalse:
	Recordset.AddNew	ResultSet.moveToInsertRow None
	VBALang.Void	void	None

  Table II presents an overview of the testing modules Constants, Functions and Type tests. The full detailed list of the results is available in validation-results.xls.

TABLE II :

 II Translation Results.

	Test case	Total Mapped Parsed Compiled	Test Result
						S	F	E
	Constants	14	1	14	1	1	0	0
	Functions	21	11	21	16	8	3	5
	Type	18	13	18	9	4	4	1
	Java Total	53	25	53	26 13	7	6
	Constants	14	4	14	14	3	0 11
	Functions	21	14	21	21 10	3	8
	Type	18	13	18	18	7 10	1
	Pharo Total	53	31	53	53 20 13 20
	Test Legends: (S)uccess, (F)ailure, (E)rror.

https://github.com/j-brant/SmaCC

To traverse the ASG as an AST and use a visitor pattern.

its implementation may vary from language to language

https://github.com/j-brant/SmaCC