Ensuring consistency between cycle-accurate and instruction set simulators

Fatma Jebali Inria Paris, France fatma.jebali@inria.fr Dumitru Potop-Butucaru Inria Paris, France dumitru.potop butucaru@inria.fr Abstract-The xMAS micro-architecture modeling language has been introduced by Intel to facilitate the formal representation and analysis of on-chip interconnect fabrics. In this paper, we introduce xMAStime, a new domain-specific language inspired by xMAS. xMAStime allows the modeling of full micro-architectures comprising certain classes of CPU pipelines, caches, and RAM. Given an in-order pipeline model in xMAStime, we automatically generate both a Cycle-Accurate, Bit-Accurate (CABA) hardware simulator and a timed instruction set simulator where time is accounted with safe upper bounds, as in the pipeline analysis step of Worst-Case Execution Time (WCET) analysis. The approach relies on the theory of endochronous systems, which allows us to ensure functional equivalence and timing consistency between the two generated simulators, using a delay-insensitivity argument. xMAStime is implemented over Lucid Synchrone -a dataflow synchronous language featuring a higher order type system and type inference, which facilitate the definition of our DSL. We use the new DSL to model and synthesize simulation code for a full-fledged MIPS32-based architecture.

I. INTRODUCTION

One key difficulty in embedded systems design is the existence of multiple models of the same hardware system, developed separately, at different abstraction levels, and used in various phases of the design flow. In the design of real-time embedded systems, we can identify:

• Cycle-accurate system models [C + 03] used to perform fine-grain hardware simulation, mostly during HW and driver design phases. These models provide an exact functional and temporal representation of system execution.

• Microarchitectural models used for pipeline simulation during WCET (Worst-Case Execution Time) analysis [START_REF] Herbegue | Hardware architecture specification and constraint-based WCET computation[END_REF], [START_REF] Herbegue | Formal Architecture Specification for Time Analysis[END_REF], [START_REF] Hardy | The Heptane Static Worst-Case Execution Time Estimation Tool[END_REF]. These models are used to compute safe over-approximations of the duration of a sequential piece of code, i.e., one function running without interruption on a processor core). To provide precise results, these models preserve much of the microarchitectural detail of processor pipelines and memory hierarchy (e.g. cache states, data transfer latencies).

• System-level models used for WCRT (Worst-Case Response Time) analysis [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF]. Assuming that the contribution of processor pipelines and caches is taken into account by WCET analysis, which provides safe upper bounds on the duration of sequential tasks, WCRT models provide the information allowing to derive system-level timing guarantees. Important information here includes the structure of the interconnect and the way resources (caches, memory banks, etc.) are shared. In this paper, we are concerned with the first two models, which are both hardware simulators with a cyclic activation pattern. Establishing semantic consistency between these two simulation models is challenging for several reasons. First, the activation pattern, which is the logical time base of the simulation, depends on the abstraction level. In cycle-accurate models, simulation cycles correspond to hardware clock ticks, whereas in WCET analysis models they correspond to changes in the program counter of the sequential program. Second, data abstractions are different in the two simulation models. Cycleaccurate simulators are often also bit-accurate, i.e. provide exactly the same results as the actual hardware. By comparison, pipeline simulators in WCET analysis abstract away most data types and related operators, typically retaining only Booleans, which can be exploited at analysis time. Last, but not least, the simulators are usually pieces of C/C++ code manually written by different teams or obtained through complex translation processes from high-level Architecture Description Languages (ADLs) that may not have a clear semantics. Formally relating such pieces of code is difficult.

Contribution. This paper proposes a method to ensure the semantic consistency between the two HW models we consider, focusing on time abstraction issues. Our method relies on desynchronization theory [START_REF] Potop-Butucaru | Concurrency in Synchronous Systems[END_REF], which defines sufficient properties ensuring that a synchronous model can be seen as an asynchronous Kahn Process Network (KPN). When a synchronous HW model satisfies these properties, any scheduling of its computations that is compatible with data dependencies will produce the same result (a property known as scheduling-independence). We show how to control scheduling through changes of the logical time base of the model prior to code generation using a synchronous language compiler. In particular, a careful choice of the logical time base allows us to produce, from the same model, either a cycleaccurate simulator, or the one needed for WCET analysis. In conjunction with some data abstraction, this logical time manipulation allows the synthesis of semantically consistent simulators from a single model.

Furthermore, we can ensure by construction that synchronous models satisfy the properties required by desynchronization theory. To this end, we introduce a new hardware modelling language, named xMAStime, allowing the compositional modeling of systems satisfying the required properties.

Outline. The remainder of the paper is organized as follows. Section II introduces both the problem and the principles of the solution we propose. Section III introduces the Lucid Synchrone language used to implement xMAStime. Section IV presents the xMAS formalism which inspired the choice of primitives of xMAStime. In Section V, we define xMAStime. We present our MIPS32 case study in Section VI. Section VIII concludes the paper and gives directions for future work.

II. MOTIVATION AND METHOD OVERVIEW

A. Motivating example

To illustrate the desired behaviour of cycle-accurate and WCET analysis pipeline simulators, we consider the twostage pipeline of Fig. 1(a). The pipeline is used to execute sequential programs with no branching. We do not detail here the function of the pipeline stages, nor the form or function of the instructions. We assume that each pipeline stage consists of exactly one unit (U1 and U2) and that the units are sequential resources, meaning that only one instruction can use a given unit at any given time. We also assume that all instructions use both pipeline stages. For each instruction, the pipeline units are used in order. For instance, I1 uses U1 on cycles 0 and 1 and U2 on cycles 2 and 3. Execution proceeds in an ASAP (as soon as possible) fashion. As soon as I1 leaves U1, it is succeeded by I2. Pipeline parallelism means that different units can execute different instructions at the same time.

The execution time of a unit may depend on the instruction and on the data. For instance, the duration of I1 on U1 is smaller than the worst-case duration of U1, which is assumed to be equal to 3 clock cycles. The worst-case duration of U2 is assumed to be 2 clock cycles.

The precision of cycle-accurate simulation, which requires the traversal of the pipeline model (to make decisions and advance simulation) at each clock cycle, has a high computational cost. To avoid this cost, instruction set simulators only traverse the model once per instruction, and may additionnally make simplifying assumptions. We are interested here in instruction set simulators that keep an accounting of time, like those used in WCET analysis tools such as Heptane [START_REF] Hardy | The Heptane Static Worst-Case Execution Time Estimation Tool[END_REF].

The functioning of such simulators is illustrated in Fig. 1(d). The use of each pipeline stage/unit is tracked with one counter initialized at 0 (the 0 figures on the left). During the simulation of one instruction, the counter of each stage used by the instruction is modified twice, to record the first and last clock cycles where the instruction uses the stage. These are respectively the left and right numbers inside each greyed rectangle. These figures are computed in a classical max-plus fashion. Executing an instruction on stage Ui can only start after the previous instruction has completed execution on Ui, and after the data dependencies of the current instruction on Ui have been solved. These dependencies are represented with arrows, and determine why, for instance, the start date of I2 on U2 is 6 = 1 + max(4, 5). The last cycle of I2 on U2 is simply computed as the first cycle plus the worst-case duration of U2.

The use of worst-case stage durations means that the start and end cycles of an instruction on a stage do not exactly match between the cycle-accurate and instruction set simulations. However, for the instruction simulation figures to be used in a WCET analysis tool, they must always be greater than or equal to the corresponding values produced through cycle-accurate simulation. In this paper, our objective is to ensure that the simulators satisfy this timing abstraction property, in addition to the functional semantics preservation due to scheduling-independence. For instance, in the cycleaccurate simulation, the end cycle of I2 on U2 is 6, whereas it is 7 in the instruction set simulation.

B. Method overview

In stark comparison with the previous example, formally stating and ensuring the functional semantics preservation and timing abstraction is challenging for complex, real-life pipelines featuring multiple stages, bypasses, register banks and hazards, etc. We propose to derive both simulators from the same hardware model in a way that ensures consistency. As modelling formalism, we rely on dataflow synchronous languages. This is natural, given that both cycle-accurate and instruction set simulations comply with the synchronous execution model [BCE + 03]. Synchronous language compilers allow the automatic translation of our models into simulation code. Furthermore, synchronous languages have well-defined semantics allowing the precise description of the concurrent semantics of pipelined hardware.

1) The two simulation levels: To illustrate the construction of two simulators starting from the same synchronous program, consider the following Lucid Synchrone program (syntax presented in Section III), meant to provide a (first, incomplete) representation of the pipeline in Fig. 1(a Listing 1: First representation of the two-stage pipeline Lucid Synchrone being a dataflow synchronous language, programs are structured as hierarchical dataflow nodes. This node represents a full system, so it has no inputs, nor outputs. The unique variable x is used to transfer data from U1 to U2. The type of x is inferred from the types of U1 and U2.

Producing two simulators from this dataflow program is done by using two versions of the U1 and U2 units. To produce a cycle-accurate simulator, where execution cycles correspond to the advancement of the HW clock, we use cycleaccurate versions of the units. For instance, to obtain the trace of Fig. 1(c), unit U2 takes two cycles between receiving an input and completing execution. Note that even units with no input or no output in the graphical representation have at least one input and one output in textual form. Drawing from functional programming, we use the special type unit and its unique value () to represent computation triggering and synchronization.

To produce an instruction set simulator, the implementations of U1 and U2 are different. Upon reception of an input they produce the corresponding output in the same execution cycle. Thus, all computations associated with an instruction are performed in exactly one execution cycle of the synchronous program. To perform the worst-case timing accounting, all dataflow variables are tagged with integer dates, which are propagated in a max-plus fashion, using the dedicated constructs presented in Section V. Note that type inference allows us to use the same program, unmodified. However, to ensure functional semantics preservation between the cycle-accurate and instruction set simulations, the two versions of each unit and the system model (the node) instantiating them must satisfy the properties defined in Sections II-B3 and II-B4.

2) In-order pipelines: The construction of the instruction set simulator, as detailed above, does not always produce a correct simulator. Consider the example of Fig. 2. Here, the pipeline has 4 units, and each of the two instructions of the program use only a sub-set of these units (U0, U1, U2 for I1 and U0, U3, U2 for I2). The pipeline also contains a demultiplexer which sends the output of U0 to either U1 or U3, and a multiplexer which takes the results from U1 and U3 and sends them to U2 in the order in which they arrived at the multiplexer. Coupled with the hypothesis that the duration of U2 is variable, this means that the order in which I1 and I2 are executed on U2 depends on the actual duration of I2 on U3. In Fig. 2(c) this duration is 3 cycles, and I1 is executed before I2. In Fig. 2(d) this duration is one cycle, and I2 is executed before I1.

We say that the behavior of this pipeline is delay-sensitive, and that it allows out-of-order execution. Clearly, instruction set simulation taking into account timing aspects is not possible for out-of-order pipelines, where the execution of an instruction may depend on subsequent instructions. The simulation code can be generated, but the simulation will be incorrect for the case of Fig. 2(d).

Out-of-order execution is a key feature of most of today's high-performance processors [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF]. This feature is usually coupled with branch prediction and multi-core cache coherency logic, making static timing analysis virtually impossible. For this reason, our work here targets simpler, more predictable processor cores, like those used in embedded processors and in many-cores (e.g. Kalray MPPA [START_REF] De Dinechin | Time-critical computing on a single-chip massively parallel processor[END_REF]).

3) Endochronous components: To determine when synchronous pipeline models can be given cycle-accurate and instruction set simulators which are consistent with each other, we rely on the theory of endochronous systems [START_REF] Potop-Butucaru | Concurrency in Synchronous Systems[END_REF].

Endochrony is a property of synchronous components, like those forming our pipelines. An endochronous component is delay-insensitive. Its behavior does not depend on the interleaving of inputs arriving on different input channels, but only on the sequences of inputs received separately on each channel. For instance, the units U0-3 and the demultiplexer of Fig. 2(a) are each endochronous, but the multiplexer is not, because the sequence of outputs depends on the interleaving of inputs arriving from U1 and U3.

Delay-insensitivity means that endochronous components can be seen as asynchronous components that are deterministic as functions from streams of inputs to streams of outputs. Thus, a pipeline formed only of endochronous components will be a Kahn Process Network (KPN) [G.74], with deterministic, delay-insensitive asynchronous semantics. Furthermore, replacing one component with another representing the same function from streams of inputs to stream of outputs does not change the (asynchronous) behavior of the KPN. For instance, replacing the cycle-accurate implementations of U1 and U2 with the instruction set simulation ones in the twostage pipeline model does not change the KPN semantics of the model if these implementations represent the same stream functions.

Endochrony is compositional, allowing the incremental construction of endochronous components (and can also be checked, albeit at a high computational cost).

4) Model-level correctness properties: In addition to the endochrony of components, our pipeline models must satisfy three supplementary propeties ensuring the correctness of the simulators and their semantic consistency. a) Isochrony: The cycle-accurate and instruction set simulation models must be correct synchronous programs. Consider the pipeline model in Fig. 3, and assume that U2 needs one input on each of its inputs to perform an execution cycle. While describing a correct asynchronous KPN, the corresponding instruction set simulation model is rejected by the synchronous language compiler because the inputs of U2 have different clocks (cf. Section III).

Requiring the correction of the instruction set simulator program ensures the isochrony of the model, the companion property of endochrony [START_REF] Potop-Butucaru | Concurrency in Synchronous Systems[END_REF] needed to ensure correct desynchronization. We require that our HW models are 1-bounded i.e. that in the asynchronous KPN interpretation of the model, regardless of the durations and triggering policies of the pipeline units, no dataflow variable may need to store more than one value at a time. The pipeline model in Fig. 1 of this model will be formally introduced in Section V. The key elements of the feedback loop ensuring 1-boundedness are the Join element that waits for one value on each input before producing them both as a pair on the output, and the two 1place buffers, initially filled with synchronization values (). The token passing mechanism implemented by these nodes ensure that U1 and U2 are used as sequential resources, and that after producing a value v, U1 can only start producing another one after U2 has consumed v.

The 1-boundedness property can be ensured by enforcing structural properties. In systems without conditional execution like the one in Fig. 4, a necessary and sufficient property ensuring 1-boundedness is that each variable is part in a dataflow cycle containing exactly one 1-place buffer that is initially filled. c) In-order execution: The final property we have to ensure is in-order execution, as introduced above. Checking that a model does not allow out-of-order execution can be done either statically, through sufficient structural properties, or dynamically by tagging all values with the instruction index and then checking at runtime that the tags never decrease.

III. LUCID SYNCHRONE

Lucid Synchrone [START_REF] Pouzet | Lucid Synchrone, version 3. Tutorial[END_REF] is a dialect of the dataflow synchronous language Lustre/Scade [START_REF] Halbwachs | The synchronous data flow programming language LUSTRE[END_REF]. It has been built on top of OCaml [LDF + 14], inheriting its higher-order type system with type inference. This allows us to use the same source code for the top-level node of both the cycleaccurate and the instruction set simulators, even though the type of the variables changes. 1A Lucid Synchrone program is formed of equations, each equation assigning values to zero or more variables. At each execution cycle of the program, a variable can be absent, in which case it cannot be used in computations during the cycle, or present, in which case it is computed once before being used with the same value in all use points during the cycle. Some variables are called clocks. They have Boolean type and are used to determine when other variables are computed or used. We say that two variables have the same clock if they are both present or both absent at each cycle.

All Lucid Synchrone statements can be derived starting from OCaml function calls2 and three dataflow primitives: merge (deterministic multiplexer), when (sub-sampling), and fby (memory between execution cycles). The inputs of a function call must all have the same clock. When the inputs are present, the function call is performed, and the outputs assigned a value. If variables a and c have the same clock and c is a clock variable, "a when c" represents a value that is present (and equal to a) only at instants where c is present with value true. Conversely, "merge c a b" has the same clock as c and the same data type as both a and b. It can be defined when c is a clock variable, and when a is present only at cycles where c is true, and when b is present only at cycles where c is false. The value output by merge is that of the present argument a or b. The value produced by "k fby a" has the same clock and type as a. The expression stores values from one cycle where a is present to the next. At the first cycle where a is present, the output value is the constant k.

Of the derived constructs of Lucid Synchrone, we shall make use of only one: the valued signals, which allow for an event-driven programming style. Each signal s can be seen a pair formed of a clock variable c_s and a data variable d_s having clock c_s. Signals are produced and read using the constructs emit and present. When executed, emit o = exp will set the clock of o to true and its value to that of exp for the current cycle. The present construct performs pattern-matching on the clocks of signals much like the match statement of OCaml performs it on regular variables.

IV. THE XMAS LANGUAGE

A. Syntax and intuitive semantics

The core of the xMAS formalism [START_REF] Chatterjee | xMAS: Quick Formal Modeling of Communication Fabrics to Enable Verification[END_REF] is a graphical dataflow language. The eight primitive dataflow operators of the language are depicted in Fig. 5, and their intuitive semantics is the following: • Upon arrival of an input x on i, a fork operator produces on each output port one value, obtained by applying to x the function associated to the port (f 1 and f 2 in Fig. 5).

• A join operator requires inputs to arrive at the same time on all input ports. When this happens, the operator sends on the output port a value computed from the input ones using the function h.

• Upon arrival of an input x on i, a switch operator sends x on the output s(x), where s(x) belongs to {0, 1}.

• The merge operator is a multiplexer. It transfers inputs to the output using a user-definable arbitration policy.

• The source and sink operators are the inputs and outputs of an xMAX specification. They respectively produce and consume messages following a user-definable policy representing the environment behavior, and the ability of the xMAS model to accept or provide a value.

• The queue is the only xMAS operator able to store values between execution cycles. A queue is a lossless FIFO with limited, specified capacity. A queue is initially empty. When full, it cannot accept inputs. When empty, it cannot produce outputs. A queue can accept input and produce output at the same time, but a value cannot be output immediately upon reception. Operators are connected through point-to-point channels, which are the dataflow arcs. Channels are reliable: they cannot create, duplicate, or loose messages.

B. Operational semantics

Semantics borrows from synchronous formalisms while introducing some nondeterminism. Execution is cyclic. At each cycle, some values can be read from source operators and from queues, some computation performed, and some values output to sink operators or stored into queues.

Execution cycles are sequences of operator actions performed according to the operator semantics defined above. However, not all sequences of actions built in this way are valid execution cycles. In addition to the obvious causality constraint that a value is produced on a channel before it can be consumed, each cycle must satisfy a global consistency constraint: Between cycles, no value can be stored outside of the FIFO queues (neither on other operators, nor on channels).

This semantics can be seen as transactional, and is difficult to implement. Existing xMAS implementations rely on a lowlevel encoding of channels based on systematic use of backpressure signaling, whose operational event-driven semantics detects valid propagation paths for data messages [START_REF] Chatterjee | xMAS: Quick Formal Modeling of Communication Fabrics to Enable Verification[END_REF].

C. Imperative xMAS

The original presentation of xMAS focuses on its dataflow part -the graphical language presented above -which is close in form and semantics to dataflow synchronous languages such as Lustre.

But xMAS is not complete without the definition of the policies governing the behavior of source, sink, and merge operators. The specification of these policies follows a very different presentation style:

• They are specified under the form of imperative code.

• Their code refers to the low-level encoding of channels mentioned above.

• They can make decisions based on the absence of dataflow values, not only on their presence. Absence can be determined with tests on the variables forming the low-level encoding of the channels. Testing the absence of dataflow values means that the behavior of an xMAS specifications may depend on the order in which inputs arrive through source operators and/or the order in which internal computations are performed, which in turn may depend on the relative speeds of the various operators. We say that, in general, xMAS specifications are scheduling-dependent or delay-sensitive.

D. Simplifications on xMAS

For presentation purposes and without loss of generality, we consider in this paper the following restrictions on xMAS:

• When an operator may have more than one input or more than one output, the number of inputs/outputs is restricted to two.

• In fork operators, the functions associated with outputs are both identity. Thus, a fork simply duplicates its input on all outputs. The combinator function of a join operator produces the pair of the two input values. Note that transformations on outputs, if needed, can always be performed outside the fork or join operator by using function call operators. For the sake of clarity, we shall also proceed to a refactoring of operators switch and merge to ensure a better orthogonality between xMAS primitives. As pictured in Fig. 6(a) we separate the routing function from the switch operator, and represent it with a separate function operator that outputs a Boolean used As pictured in Fig. 6(b), we separate the arbitration policy from the merge operator. The arbitration decision is represented as a Boolean input to Merge, determining which input must be transmitted to the output. Unlike in switch operators, the arbitration decision cannot always be computed using a simple function operator. For instance, the representation of classical Round-Robin arbiters [START_REF] Chatterjee | xMAS: Quick Formal Modeling of Communication Fabrics to Enable Verification[END_REF] requires making decisions based on the absence of values on inputs, which is done with tests on the state of the low-level channel encoding. In such cases, we encapsulate the low-level decisions into source operators whose input values and policy correspond to the computation of the arbitration decisions, as pictured in Fig. 7. Previous work on xMAS showed that its set of primitives provides the good mix of asynchronous and synchronous features for the description of complex interconnect fabrics for verification purposes. Our experiments showed that the xMAS primitives also allow the description of full architectures, including CPU pipelines. They allow the natural representation of asynchronous pipeline interlocking (as in Fig. 4), instruction dispatch to functional units (as in Fig. 2) and the complex behavior of register files, as in the MIPS32 example of Section VI.

However, the non-deterministic and transactional semantics of xMAS does not provide good support for the synthesis of efficient simulation code. We introduce here a new language based on xMAS but with synchronous semantics, that facilitates the specification of complex pipelines and at the same time allows efficient code generation using an existing synchronous language compiler.

The new formalism is called xMAStime. As earlier explained, from each xMAStime model we derive two synchronous programs corresponding to the two simulation levels we target. The simulators are obtained by compilation of the two synchronous programs, when the correctness properties of Sections II-B3 and II-B4 are respected. To attain this workflow, we implemented xMAStime on top of the Lucid Synchrone language presented in Section III. More precisely, xMAStime is an API with two implementations. The xMAStime models are developed using only primitives of this API. Then, the synchronous models corresponding to the cycleaccurate or instruction set simulators are obtained by using the corresponding API implementation. We describe here the API and its two implementations.

A. The xMAStime API

An xMAStime model is a Lucid Synchrone program-a dataflow node. Its inputs and outputs are represented in the interface of the node, and not (like in xMAS) with dedicated primitives. The use of Lucid Synchrone's module system, which xMAS does not have, facilitates the modular construction of complex architecture models. But the difference is not merely syntactical. The sink and source xMAS primitives allow the specification of production and consumption policies, which cannot be directly expressed in xMAStime. This is not an issue, because xMAStime is meant to represent full hardware architectures evolving in isolation, and not parts thereof. Like in Listing 1, the main node of an xMAStime model must have no inputs and no outputs, as it describes a CPU accessing its own RAMs to perform computations without interrupts from the environment. Interaction with the environment can be modeled as the sampling of memory-mapped devices. The queue construct of xMAS is replaced in xMAStime with the fby statement specific to dataflow synchronous languages, hence its classical graphical representation. This will allow the direct use of Lucid Synchrone's synchronous semantics to interpret the resulting specifications. It is important to note that the behavior of the synchronous fby can be implemented in xMAS using the construction of Fig. 8. Note the complex initialization circuitry needed to bring the v0 value from a source to the initially empty queues.

The last construct is the time accounting primitive, with no direct counterpart in either xMAS or Lucid Synchrone. To preserve the close syntactic proximity with xMAS, we require that each variable (including node inputs) is used as input in at most one primitive. In other words, the use of broadcast is replaced with that of xt_fork.

B. API implementation

The implementation of the xMAStime API is provided in Listings 3-5 and Listings 7-10. Recall from the motivating example that time advancement is encoded in a different fashion in cycle-accurate and instruction set simulations. In instruction set simulation, time must be explicitly represented with tags annotating the values transmitted through dataflow variables. This is the case in Listing 2 (lines 7-9), where the input value is first decoded as a pair formed of the data value and its time tag. The output is constructed from the computed data value f(i_val) and the tag received as input. Note that, in line with synchronous language modeling, function computations do not take time.

Tag modification follows a max-plus approach. Each primitive receiving multiple inputs (such as xt_join, in Listing 3, lines 11-14) will compute the output tags as the maximum of the input ones. Accounting for operation durations is done with the xt_time_delay primitive (Listing 5, lines 25-27), which adds to the tag a value computed from the input data value using the provided delay function. To model a functional unit and its duration, one needs to use an xt_fcall primitive for the functional part, and an xt_time_delay primitive to account for the duration. In cycle-accurate simulation, the simulation clock is the clock cycle of the architecture and it counts the advancement of time. We no longer need time tags associated with dataflow values. The difficulty here comes from the fact that the operations of primitives such as xt_join or xt_time_delay are no longer instantaneous, and their duration may depend on data values (e.g. delta in Listing 5). The Lucid Synchrone compiler is no longer capable of automatically inferring the relations between activation conditions of the primitives, and we need to resort to a more asynchronous programming style. We do this using the signals of Lucid Synchrone, which are emitted and whose presence can be tested using dedicated primitives. In cycle-accurate simulation, all dataflow variables are signals. In Listing 2 (lines 2-5), the cycle-accurate implementation of xt_fcall will emit a value f(v) on the output o whenever i is present with value v.

We are now ready to provide (in Listing 6) the xMAStime textual source of the two-stage pipeline of Fig. 4. The listing contains the main node simple_timed and the auxiliary node xt_resource that models a resource whose functionality is provided by function f and duration is provided by function delay. The data processing and duration computation functions, which can be defined in OCaml, are not provided. Note how xt_resource uses the delay function to aliment the xt_time_delay primitive which accounts for the duration of the resource computation. Listing 6: Two-stage pipeline, 1-bounded model C. Correction considerations 1) Method-related artefacts: Notice that the cycle-accurate implementation of certain xMAStime primitives contains error conditions, implemented with the failwith construct of OCaml, which raises a Failure. The use of exceptions may be surprising in a "correct-by-construction" modeling method. However, the reason for this is simple: the asynchronous programming style based on signals means that the overall correction of the application, in the sense of Sections II-B3 and II-B4, cannot be inferred by the Lucid Synchrone compiler. For instance, the compiler cannot infer the 1-boundedness of the application, and therefore requires the programmer to provide code covering buffer overflow cases e.g. when a xt_join receives two values on one input and none on the other.

For specifications that satisfy the required correctness properties, the error handling code is unreachable. Simplifying the programming of the primitives and the generated code by removing this dead code would require a dedicated compiler, able to verify the respect of the xMAStime-specific correctness properties. Our current solution, where error handling code still exist, but only inside the primitives (and not in their interfaces), seems a good compromise between ease of implementation (for language prototyping) and time investment into development tools.

2) Functional semantics preservation and timing abstraction: For each xMAStime primitive, the two implementations are endochronous and correspond to the same function from streams of inputs to streams of outputs. According to II-B4, if the compiler can generate code for both simulators, and if no run-time errors occur in the cycle-accurate simulator3 then the functional semantics is preserved. If the specification is also in-order, then the start and end dates of each instruction on each pipeline unit are equal in the two simulations.

Note in the definition of xt_resource that the duration of pipeline resources may depend on their input (it is computed by applying function delay to the input data). To perform timing accounting in the worst case, as needed during WCET analysis, this function must be replaced with the constant function returning the worst-case value. Data abstraction can be handled in the same way, by replacing the data types and data processing function with abstracted versions.

VI. THE MIPS32 CASE STUDY

We applied our modelling approach on a full-fledged architecture featuring a MIPS32 CPU core. The architecture is of Harvard type, with separate instruction and data memory banks and separate L1 caches, both with a LRU (least recently used) replacement policy. The resulting model is used to generate a cycle-accurate simulator and an instruction set simulator. Simulation is performed in isolation: the memory is precharged with the sequential program to run and with the values of initialized data, and execution proceeds without interaction with the environment.

The design takes advantage of the modularity of Lucid Synchrone. The top level node of our model is pictured in Fig. 9. Like in previous figures, named boxes correspond to instantiations of other nodes. For instance, Fig. 10 provides the implementation of the memory access node.

Our MIPS32 model uses a classical 5-stage pipeline implementation [START_REF] Hennessy | Computer Architecture: A Quantitative Approach[END_REF] (fetch/decode/execute/memory access/write-back). Execution is fully in-order. The interlocking protocol implemented using xt_fby primitives ensures 1-boundedness. The construction of the interlocking protocol is simplified on the MIPS32, due to the existence of delay slots.

The register file is placed inside the node implementing the decode stage, but it is also accessed by the write-back stage. Pipelined stages run concurrently, so there may be situations where the content of the registers to be read in the decode stage depends on the result produced by a preceding instruction that is still in the pipeline. Such a situation is called a data hazard. The sequential execution semantics of the program is preserved by allowing later pipeline stages to freeze earlier stages until the preceding instruction has finished updating the registers in the register file. In Fig. 9, the protocol allowing this is implemented using a single feedback line from the writeback node to the instruction decode node.

All data types and data handling routines of the model are defined in OCaml. Particularly complex pieces of this code implement instruction decoding and cache policies. Of the MIPS32 ISA we did not implement the optional floating point unit (FPU) instructions. Also in OCaml are implemented all the functions computing the duration of the various units.

VII. RELATED WORK

Architecture modeling for the real-time is not a new subject ( [HFC14], [START_REF] Cassez | Timing analysis of binary programs with uppaal[END_REF] provide a good overview). Traditional approaches are based on the use of Architecture Description Languages (ADLs) which allow the modeling of modern architectures, but do not have clear semantics. The semantics of the artefacts (simulators, analysis models, synthesizable RTL) obtained from these models is largely dependent on the translation tool, making it difficult to establish formal semantics preservation between artefacts.

More recently, [START_REF] Herbegue | Formal Architecture Specification for Time Analysis[END_REF] gave formal semantics to an ADL tailored for timing analysis. This is done by means of constraint programming, allowing the use of constraint solvers to compute the WCET of basic blocks on complex architectures with out-of-order execution [START_REF] Herbegue | Hardware architecture specification and constraint-based WCET computation[END_REF]. Given that the formal timed semantics is basically that of the WCET analysis model and is not operational, it is not clear how easy it is to relate it with the semantics of simulation models of the same architecture. By comparison, we target simpler architectures, with the objectives of 1) highlighting how theoretical principles allow establishing formal semantics preservation results for both functional and timing aspects and 2) embodying these principles in easy-to-use DSLs allowing experimentation.

The xMAS formalism has a formal operational semantics, but the transactional form of this semantics mainly supports the formal modeling and verification of functional properties of communication fabrics [START_REF] Chatterjee | xMAS: Quick Formal Modeling of Communication Fabrics to Enable Verification[END_REF]. The synthesis of Verilog and C++ executable code is also possible [ZL17], allowing cycle-accurate simulation, and network calculus has been used to compute performance bounds on the communication fabric models. By comparison, our xMAStime formalism gives up non-determinism and is used to represent full-fledged architectures. It explicitly covers timing aspects and allows establishing semantics preservation guarantees between two different simulation levels.

Our work is also strongly related to the large corpus of results on high-level synthesis (a good overview in provided in [TKE17]). When the high-level specification has a welldefined formal semantics that is preserved in the implementation, the equivalence between different synthesis outputs (e.g. synthesizable RTL which is amenable to cycle-accurate simulation and functional simulation code, as is it possible using synchronous languages [BCE + 03]) is acquired by construction. The originality, in our case, is that the semantics of the implementations can be transposed in the high-level model, through the change in logical simulation clock, which changes scheduling. Also, our semantics preservation guarantees cover timing aspects.

VIII. CONCLUSION

We proposed an approach for the construction of mutually consistent cycle-accurate and timed instruction set simulators of full micro-architectures comprising CPU pipeline, caches, and RAM. The method is theoretically founded on desynchronization theory. It is fully tooled, and has been showcased on a full-fledged MIPS32-based architecture.

On the application side, ongoing work aims at integrating the generated simulators with the SoCLib cycle-accurate simulator and WCET analysis tool used in [PP13]. The current method is restricted to single-core in-order architectures that can be given delay-insensitive models. In future work, we will extend our approach to allow limited recourse to speculative execution and out-of-order execution, by safely approximating delay-sensitive timing behaviors with a delay-insensitive ones. We will also investigate the representation of timing compositional multi-core architectures.

Fig. 1

 1 (c,d) provides graphical representations of the pipeline simulations we want to obtain for the two-instruction program in Fig. 1(b). Cycle-accurate simulators, like those implemented using the SoCLib platform [C + 03], describe the exact behavior of the modeled hardware. A cycle-accurate simulation is driven by the advancement of the hardware clock (clk in Fig. 1(c)).

Fig. 1 :

 1 Fig. 1: Two-stage pipeline (a), two-instruction program (b), cycle-accurate simulation (c), instruction set simulation (d)

): 1

 1 let node simple () = () where 2 rec x = u1( () ) 3 and ( ) = u2(x)

Fig. 2 :

 2 Fig. 2: Delay-sensitive, out-of-order pipeline (a) with a program (b) and two possible execution traces (c,d). Program comments provide the units used by each instruction.

Fig. 3 :

 3 Fig.3: Non-isochronous pipeline model b) Boundedness: In the original definition of KPN, communication channels are lossless unbounded FIFOs that can accumulate incoming values waiting consumption. However, synchronous models and real hardware do not allow such an accumulation process. To ensure the absence of accumulation, processor pipelines rely on both timing arguments and on feedback mechanisms. For instance, the model in Fig.1(a) is not bounded. If the duration of U1 is 2 and that of U2 is 4, then in an ASAP execution model U1 produces twice as much values as U2 can consume, the rest being lost/overwritten.We require that our HW models are 1-bounded i.e. that in the asynchronous KPN interpretation of the model, regardless of the durations and triggering policies of the pipeline units, no dataflow variable may need to store more than one value at a time. The pipeline model in Fig.1(a) can be completed to a 1-bounded model as pictured in Fig.4. The elements

Fig. 4 :

 4 Fig. 4: Two-stage pipeline, 1-bounded model

Fig. 5 :

 5 Fig. 5: The xMAS primitives

Fig. 6 :

 6 Fig. 6: Refactoring xMAS primitives

Fig. 7 :

 7 Fig. 7: Refactored fair arbitration using a source

Fig. 8 :

 8 Fig. 8: xMAStime API and corresponding xMAS primitivesThe API proper contains seven primitives, listed in Fig.8along with their intuitive xMAS and dataflow synchronous correspondent. For the first five primitives, the correspondence with both the xMAS counterpart (in the simplified version we introduced in Section IV-D) and a dataflow synchronous

1

  ( * cycle-accurate implementation * ) 2 let node xt fcall (static f ) i = o where 3 present 4 | i (v) -> do emit o = f (v) done 5 end 6 ( * instruction set simulation implementation * ) 7 let node xt fcall (static f ) i = o where 8 rec (i val ,i tag) = i ( * separate tag from value * ) 9 and o = ( f (i val ) ,i tag) ( * tag remains unchanged * ) Listing 2: Implementation of xt fcall

1| 9 ||||

 9 ( * cycle-accurate implementation * ) 2 let node xt join (i1 , i2) = o where 3 rec (o1, v1) = buffer1 (i1 , c) 4 and (o2, v2) = buffer1 (i2 , c) 5 and clock c = (?i1 | | (v1 != None)) && (?i2 | | (v2 != None)) 6 and emit o = match (o1 when c, o2 when c) with 7 | (Some x1, Some x2) -> x1, x2 8 | -> failwith "xt join" 9 end 10 ( * instruction set simulation implementation * ) 11 let node xt join (i1 , i2) = o where 12 rec (i1 val, i1 tag) = i1 13 and (i2 val, i2 tag) = i2 14 and o = ((i1 val , i2 val) , (max i1 tag i2 tag)) Listing 3: Implementation of xt join 1 ( * cycle-accurate implementation * ) 2 let node xt fby (static def) i = o where 3 rec emit init sig = def 4 and o = init sig fby i 5 ( * instruction set simulation implementation * ) 6 let node xt fby (static def) i = o where 7 o = def fby i Listing 4: Implementation of xt fby Note that Lucid Synchrone nodes can have static parameters, which are not dataflow variables. Static parameters are fixed and do not change during node execution, like the function executed by xt_fcall. 1 ( * cycle-accurate implementation * ) 2 let node xt time delay (delta, i ) = o where 3 rec inp = present 4 | (xt join (delta, i ))(d,x) -> let a = (d,x) in Some a 5 Some a, Some b -> let (di , xi ) = a and (dp,xp) = b in 10 if dp = 0 then (Some xp, Some a) 11 else failwith "xt time delay overflow" 12 Some a, None | None, Some a -> 13 let (d,x) = a in 14 if d = 0 then (Some x,None) 15 else let b = (d -1,x) in (None, Some b) 16 None, None-> None,None 17 end 18 and prev = None fby nxt 19 and clock c = (osample< > None) 20 and emit o = match osample when c with 21 Some x -> x 22 | None-> failwith "xt time delay unreachable" 23 end 24 ( * instruction set simulation implementation * ) 25 let node xt time delay (delta, i ) = o where 26 rec (i val ,i tag) = i 27 and o = (i val , i tag + (delta i )) Listing 5: Implementation of xt time delay

1

  let node xt resource (static f ) (static delay) i = o where 2 rec (i1 , i2) = xt fork i 3 and x = xt fcall f i1 4 and o = xt time delay ( xt fcall delay i2 , x) 5 6 let node simple timed () = () where 7 rec x = xt resource f1 d1 (xt fby () ( xt fcall snd sync1)) 8 and sync2 = xt resource f2 d2 ( xt fcall fst x2) 9 and (sync1, x2) = xt fork x1 10 and x1 = xt join (x, (xt fby () sync2))

Fig. 9 :Fig. 10 :

 910 Fig. 9: Top-level view of the MIPS32 model

For instance, in instruction set simulation, all variables are tagged with an integer date, which is not needed in cycle-accurate simulation.

Tuple operations can also be seen as function calls.

This can be statically ensured through 1-boundedness.


Steven Costiou
email: costiou@univ-brest.fr

Mickael Kerboeuf
email: kerboeuf@univ-brest.fr

Alain Plantec
email: plantec@univ-brest.fr

Marcus Denker
email: marcus.denker@inria.fr

Seeking and Finding Objects at Runtime with Collectors

Keywords: Software and its engineering → Maintaining software, Software prototyping, Object oriented frameworks, Integrated and visual development environments, Object oriented development, Object Oriented Debugging, Debugging, Object Tracking ACM Reference Format:

come

INTRODUCTION

Interacting with running programs is interesting for many reasons, for example monitoring applications, reverse engineering, debugging... For such interaction, the first abstraction we can look for is the source code, that we can modify to see changes of behavior and get feedback. But at runtime, we may want to interact with abstractions closer to our programming paradigm. In object-oriented programming we would look for objects, as they are the main entities that structure our programs. Behavior is expressed through the classes of these objects, in which methods are defined. Within the control flow of these methods, we will find other objects referenced by instance variables or temporary variables. It is tempting to adopt a pure object-centric view [START_REF] Ressia | Object-centric debugging[END_REF]. We would see these variables in the source code as objects that we can interact with. In the end, we would deal with objects instead of using exclusively source code.

From this point of view, imagine a developer who is debugging a running program, and is looking to its source code. One of the objects in particular is of interest and should be, for example, logged somewhere. The developer could look for instances of this object's class in the running program -which would be a very tedious task if performed manually. He/She could also look where this class is instantiated in the code, then dig into the running program's structure and try to find objects of interest. This can also be very tedious if multiple objects of different classes should be targeted, and even impossible for objects with very short lifespans if the program is still running. Moreover, it becomes a bit more complex in dynamically typed systems, like Smalltalk, Python or Ruby. In programs written in these languages, there is no guarantee that a reference in the code will always be of the same type [START_REF] Milojković | It's duck (typing) season![END_REF]. The developer could also try to locate positions of interest in the code, e.g. after a temporary variable is assigned, and insert code that somehow mark the object, so that it can easily be retrieved while the program is executing. This could be very intrusive, especially if the inserted code should check for conditions before marking the object. It also makes it unpractical: What if the developer wants to change the condition? How to ensure that the base code is not polluted by manual instrumentations that could be forgotten by the developer?

To help the developer interact with objects from the variables in the source code, we introduce the Collectors. Collectors are first-class objects that target entities in the source code. Objects referenced by these targets will be collected at runtime, and presented to the developer. Collectors provide a non-intrusive way of gathering objects during the program execution and to interact with them. They are available through an API that provides means to:

(1) Dynamically specify in the control flow which object must be collected

(2) Scope the collection of objects to specific conditions or to specific entities (classes or objects) (3) Provide references to the collected objects and means to interact with them at runtime The contribution of this paper is the description of the Collectors solution and its API. On top of this API, we describe and show an implementation of the Collectors tool-set in Pharo Smalltalk [START_REF] Andrew P Black | Pharo by example[END_REF]. It provides integrated support for the object-centric views and interactions brought by Collectors. It is completed by an illustration of object collection and logging in a running, remote IOT application.

The paper is organized as follows: Section 2 explains the problem through a simple example. Section 3 introduces Collectors. Section 4 demonstrates Collectors through a simple IOT application and Section 5 discusses the Collectors solution and its limitations. Sections 6 explores other possibilities and related work. We conclude in Section 7 with working directions and a summary of the Collectors proposition.

THE PROBLEM

We consider the case of running object-oriented programs, for which the developer needs to interact with specific objects. This need may come from various reasons, for example debugging. A developer may want to find objects of interest, e.g. to change their behavior or to log their state. Looking for these objects can be a problem because this need appears at runtime. A first research could provide some results, but it may need to narrow down this search to find more specific objects. That is often the case while debugging, when exploring a runtime behavior to find bugs. Furthermore, the objects found may have been changed in some way by the developer, e.g. through behavior adaptation. In that case they must be referenced somewhere if the developer wants to revert these changes in the future. In the following, we describe and emphasize this problem through an example of code written in a Smalltalk fashion.

The IOT application example

Let us imagine an IOT application on a device with a temperature sensor and a light sensor. The application has a main class IotApp which runs a loop. Every second in this loop, the IotApp reads the temperature and the light from the sensors. The GenericSensor class models common behaviors and interface of all sensors. It implements a method #readChannel:, which queries the sensor and returns an interpreted physical sensor read. As shown in Listing 1, this method takes an object as a parameter.

A physical sensor read is performed by an instance of class SensorRead, in the #read: method. This method reads a physical address, interprets the raw value if necessary, then returns the value. In the code above, channel is declared as a temporary variable (first line). At the end of the method, the ˆsymbol returns the result of the sensor read. The GenericSensor is specialized into two subclasses: TemperatureSensor and LightSensor. These classes model temperature and light sensors that use the #readChannel: method from their superclass. Instances of these class are referenced by two instance variables in the IotApp class: temperatureSensor and lightSensor.

The problem

This application is running on a remote device. Let us suppose that we have a remote access to the application. We would like to log the state of specific objects, so we need to find those objects. Pharo Smalltalk [START_REF] Andrew P Black | Pharo by example[END_REF] for example provides reflective capabilities and tools to interact with running programs. It allows the developer to find references to objects. We could send the message #allInstances to a class to recover all instances of this class. Then it would be possible to find one of these instances, to inspect its structure, its relations, its state and find the objects we are interested in. It seems granted that any object could be found and modified at runtime. However, we expose below three cases for which introspection capabilities do not suffice to find objects of interest in a running program: the limited lifespan object case, the "anonymous" object case and the multiple instances case.

The limited lifespan object case. We call "limited lifespan objects" entities that are non-permanent objects or states, that exist only for a very limited amount of time before being garbage collected. It makes it impossible for the developer to find those objects by inspecting the state of another object at runtime. Typically, these objects are referenced by temporary variables, objects instantiated within a local scope, and instance variables of these latter objects. This case is illustrated in Listing 1 where the channel temporary variable never exist long enough to be inspected. We can also see in Listing 1 that the lifespan of instances of SensorRead, and by extension their instance variables, are scoped by the #readChannel: method execution.

The "anonymous" object case . Such "anonymous" objects are instantiated objects to which cascaded messages are sent and the execution result is returned without storing the object in any temporary state. This is the case in Listing 1, where an instance of SensorRead is created and never stored. There is no variable to inspect, and the developer would have to halt the system and inspect the stack to find the object.

The multiple instances case . In this application there could be other sensors than the temperature sensor. All these sensors would be modeled by subclassing the GenericSensor class, and all objects would share the #readChannel: method from Listing 1. Modifying the method will impact all objects sharing it. But when probing the system, we may be interested only by the SensorRead objects created by instances of TemperatureSensor, and not all existing instances using the method throughout the execution of the application.

Why it is not trivial

Imagine that the developer wants to do the following: Each time a SensorRead object is created by the temperature sensor, then its state is logged in a console. He/She will be facing the three problematic cases described above. First, dynamically inserting logging instructions in the #readChannel: method where the objects are created (Listing 1) will not work, as a modification of this method will impact all instances of classes using it and not only the temperature sensor. Second, the SensorRead objects have limited lifespans in this method. Getting them manually by inspecting the program is excluded. Finally, those objects are never stored so that there are no explicit references to them. There are no practical ways to find them with a debugger, or without complex instrumentation of the code. Such instrumentation would imply inserting variables and adapting the code to provide references to objects. Moreover, these operations must not alter the original behavior of the method.

It becomes more complex if the wanted object must satisfy a specific condition, for example: Each time a SensorRead object created by the temperature sensor has a value lower than zero then its state is logged in a console. In addition, this condition could dynamically change if the developer wants to narrow it down. And if at some point during execution, the modified behavior of these objects is not necessary anymore, all behavior changes must be reverted. The code we presented as an example is very simple, and yet we can illustrate three cases where it is not trivial to find specific objects at runtime for a simple case of logging.

COLLECTORS

In this Section we present the Collectors, that allow the developer to dynamically collect objects from the control flow and to interact with them. They provide references to collected objects, so that the developer can freely manipulate them. Collectors are composed of:

• A programming interface to specify which object to collect in the control flow and how to interact with them • A set of tools to help viewing the source code as objects references with which we can interact Objects that can be collected are (1) objects referenced by temporary variables, (2) by instance variables or (3) receivers of specific messages in the control flow. These kind of collection can be performed either through the Collectors tools or through their programming interface. Collectors can be specified either before or during runtime. The following subsections describe the Collectors tools, API, model and its implementation for object-oriented languages.

Collectors model

Collectors are first-class objects. They can be installed and released at runtime through their API. Their purpose is to collect references of objects at strategic places in the control flow of methods. How this collection is done depends on how it is specified for each collector. One collector can collect either:

• Objects referenced by a temporary variable, each time it is accessed • Objects referenced by a slot, each time it is accessed • Objects receiving a specific message For a given collector, object collection is performed each time the collection condition is met within the specified control flow. An object collection is permanent, unless the collector is released by the developer, or the object is garbage collected or the collector specification changes. In that latter case, all objects are released before the collection can start again. It is the case if the developer adds a condition or a scope to the collector.

Collectors cannot be composed themselves, i.e. they can target only one of the items enumerated above. A Collector collecting an instance variable cannot collect temporary variables. However it is possible to compose a global object collection strategy by creating multiple collectors.

Objects are released if reclaimed by the memory handler (garbage collector, manual release...). Collectors only hold weak references of objects, and never interfere with the program memory management. Interaction is only possible during the object lifetime. Similarly, a single object cannot be collected more than once. If a collector attempts to collect an object already collected, then the reference that it holds is not duplicated.

Collectors API

In the following we describe the Collectors programming interface in a Smalltalk fashion. The Collector class provides the global interface to define collectors, while its instances provide means to interact with the collected objects. The API can be used both at development time and at runtime. Collectors specification and modification is dynamic, provided the host language features means to interact with the running program.

Specifying which entity to target. A collector can collect either (1) objects referenced by a temporary variable, (2) by an instance variable or (3a, 3b) by the receiver of a message. The result of each API call returns a collector object. It is stored in a global collection and can be accessed at any time. In the following, the words preceded by a '#' character are parameters passed to the API. The class keyword means these methods are static class methods. (1) Collecting objects referenced by a temporary variable, within a single method. It is performed each time the instance variable is accessed (read/write).

Collector class>> collectTemporary: #tempName in: #methodName fromClass: #className.

Figure 1 shows how objects referenced by a temporary variable named temp are collected in a dummy method. Each time the temporary variable is accessed, the object it references is collected (line 2, 6 and 7). The collection is performed after the variable has been read or written. On a write access, the object is collected after the value is stored in the variable. In that case, it is that new value that is collected (lines 2 and 6). If the variable accessed references an object that has already been collected, the object is not collected twice. We can see this case at line 6 and 7), where a collection is attempted two times in a row for the same object stored in temp. (2) Collecting objects referenced by an instance variable. It is performed each time the instance variable is accessed (read/write).

Collector class>> collectInstVar: #ivarName fromClass: #className.

Collecting an instance variable follows the same pattern as the temporary variable collector. All using methods of the target instance variable will trigger object collection after a read or a write to this variable. This collection pattern is illustrated in Figure 2, where the ivar instance variable is collected. In that case, the ivar instance variable will also be collected each time another method accesses it.

(3a) Collecting objects to which a message is sent, within a single method. Every object receiving the message is collected.

Collector class>>

collectReceiversOf: #messageName in: #methodName fromClass: #className.

Figure 3 shows the collection of objects receiving an #add: message. Like the instance and temporary variable collectors, the collection is performed after the message is received by the object. All objects receiving the specified message within the method body are collected when the code executes, regardless of their class (lines 4 and 7). (3b) Collecting objects to which a message is sent, within a single method. Only a target object receiving the message within a single statement is collected. This collector is specified by passing an abstract syntax tree node (#anAstNode) representing a message send. This interface is less practical to use as is, because the developer has to dig into the AST of a method to find the appropriate AST node.

Collector class>>

collectReceiverOfNode: #anAstNode.

Figure 4 shows the collection of objects receiving a message at a specific place in the control-flow. Other objects receiving the same message but elsewhere in the control-flow are not collected. Object collection is also performed after the message is received, and regardless of the receiver's class.

Accessing and releasing collectors. All collectors present in the system can be retrieved at once, and the developer can browse this list and select a particular collector. Collected objects are stored in weak references. They can be retrieved and enumerated. Finally, the developer can release the collector. It will stop collecting objects and be removed from the Collectors global collection. Multiple entities can compose a scope for a given collector. They can be classes or individual objects. Object collection is performed only if one of the scoping entities executes a statement for which a collector is defined.

Defining actions for collected objects. The user can specify an action to be performed each time an object is collected or released. There is only one possible action for the release and for the collection. It takes the form of a block closure with two parameters, namely the collected object and the collector that collected this object: Conditioning object collection. A collector can be configured to collect only objects satisfying a specific condition. The condition is evaluated each time a collector attempts to collect an object. The condition takes the form of a block with one or parameters, namely the object or the object and its context:

collector condition: aBlock
For example, we can condition the object collection to only collect objects with a specific state: collector condition:

[:object :context| object class hasSlotNamed: #someState].

Collectors Tools

Collectors provide tools to help the developer specify object collection and interaction. All the tools allow dynamic interaction with the source code representing objects. Object collection can be specified before or at runtime, on a program running locally or on a remote device (e.g. an IOT object). The tools presented below are from a Pharo Smalltalk [START_REF] Andrew P Black | Pharo by example[END_REF] implementation of Collectors.

3.3.1

The control-flow object selector. The developer can ask for object collection through a new contextual menu, which is integrated in the code browser of Pharo. In any method that is browsed by the developer it is possible to define a collector. This menu allows the collection of objects references by instance and temporary variables, and to which a message is sent.

Figure 6 shows the contextual menu spawned in a method from the code browser. In this example, the receiver of the #read: message will be collected. This object collection is made through the control flow. Only the object receiving this message at this particular place will be collected.

Other objects receiving the same message within the same method but in another statement will not be collected. The source code displayed in native code browsing tools is not altered by collectors.

The Collectors browser.

The Collectors browser provides the developer with a view on all defined collectors. From this view, one can explore collected objects, define actions to perform at collection and at release time, express conditions for object collection and explore entities to which the collector is scoped. This is illustrated in Figure 5. The browser shows the list of active collectors (A). Collectors can be renamed through a contextual menu to help the developer identify their meaning. Collectors specifications are shown in (B).

For example, in Figure 5, we see that the object that will be collected is the receiver of the #read: message after it has been sent. The part of the code representing this object is automatically highlighted by the browser. The collector specification is the only aspect of the collector that cannot be changed dynamically.

To collect objects from another part of the control flow, a new collector must be defined. In (C) we can see the collect and release actions. These actions are performed at collect or at release time. This feature can be used to perform direct actions on collected objects, or to pass them to another mechanism (e.g. an adaptation mechanism).

Actions can be defined and changed dynamically, by coding them in the browser and saving them through the contextual menu. The defined actions are applied to the next object collection or release, but not to already collected or released objects. (D) shows a condition for object collection. Objects are collected only if the condition is met. By default the condition is disabled. Like the collect/release actions, the condition can be dynamically changed through the browser editor and only apply for the next object collection. Finally, in (E), we can see entities to which the selected collector has been scoped.

For instance, the collector named Receiver of #read: is scoped to an object aTemperatureSensor instance of a TemperatureSensor class. It means that object collection will be performed only if this object goes through the control flow highlighted in the specification pane (i.e. in (B)). This scoping is dynamic and can evolve at runtime, and multiple entities can scope the collector (classes and objects). The browser allows the user to browse these entities through a contextual menu.

Scoping collectors to objects.

Collectors add a new pane to the native Pharo inspectors. Upon inspection of an object, it is possible to see the defined collectors in the program. A contextual menu allows to scope the collection operation to the current inspected entity. Once scoped, a collector will perform object collection only if the entity to which it is scoped goes through the adequate control flow. An example is shown in Figure 7. We can see an inspector on an instance of a TemperatureSensor class. In the collectors pane we can see all defined collectors. We could, for example, scope the collector defined in Figure 6 to the inspected temperature sensor. This collector will then collect objects only when the temperature sensor object executes the #readChannel: method.

Implementation

We implemented Collectors with Pharo [START_REF] Andrew P Black | Pharo by example[END_REF] and we rely on the Reflectivity layer [START_REF] Nierstrasz | Model-centric, context-aware software adaptation[END_REF] to inject non-intrusive annotations on abstract syntax tree of methods. These annotations give us access to reifications of the running program, which are instance or temporary Methods for which Collectors are specified are recompiled for the collection behavior to be active. However that is transparent to the user, and to the environment tools. There are no visible instrumentations when the user looks at the code. Collectors instrumentations do not interfere with the original behavior of the code. A downside is that if the user manually modifies an instrumented method, the original behavior is restored and the collection behavior is removed.

Alternative to Reflectivity, Aspect oriented techniques could serve as another back-end a Collectors implementation. We made experiments of such implementation with PHANtom [START_REF] Fabry | PHANtom: a modern aspect language for Pharo Smalltalk[END_REF]. This implementation is partial and scoped to the collection of objects receiving a given message.

EXAMPLE ON AN IOT APPLICATION

In the following, we demonstrate the use of Collectors in an IOT application. This example features a simple case of debugging where a developer wants to add log on specific objects in the running system. The difficulty, as explained in Section 2, is to identify those objects and to get references to them for interaction. Results and demonstration of the experiment are available online. 1

The Sensor Monitoring Application usecase

As an illustration, we used the Sensor Monitoring Application usecase [START_REF] Marra | Debugging Cyber-Physical Systems with Pharo[END_REF]. It is a single threaded Pharo IOT application deployed on a Raspberry Pi 2 in which there is an unpredictable bug at runtime. The bug comes from an erratic sensor read that may happen at any time during the execution of the program. From the original use-case we slightly changed the setup to fit our example, which now uses two sensors (temperature and light). We deployed the code from Section 2 as the main sensor access in the application. As shown in Figure 8, the developer is remotely connected to the application through Telepharo, the Pharo remote debugger. All operations described below are executed at runtime. The unanticipated logging operation While debugging the Sensor Monitoring Application, we suspect a problem in the temperature sensor readings. So we would like to log SensorRead objects in a console when their values become erratic. We would also like to scope this logging to SensorRead objects created by the temperature sensor, and not all of them that may be created by other entities in the system. As there is no way to predict when the erratic values may appear it is impossible to know when to start logging. We also cannot distinguish sensor readings created by the temperature sensor from the ones created by others sensors. That is because all sensors share the same method #readChannel: from their super class, as described in Section 2. It is complicated to know which are the objects that should be investigated.

Collecting and adapting objects

In the following, we describe how we used the Collectors API in the IOT App to collect sensor readings objects and to log them into a console. We programmatically use the API, but all of the operations below can be performed in an interactive way using the tools described in Section 3.3.

Collecting all SensorRead objects. We want all instances of SensorRead to be logged in a console. They are instantiated in the #readChannel: method from the class GenericSensor (see Listing 1). To collect them, we have to ask for the receivers of the #read: message which is sent just after their creation: collector := Collector collectReceiversOf: #read: in: #readChannel: fromClass: #GenericSensor.

The collector will collect all objects receiving a #read: message in the specified method. Fortunately there is only one receiver of 2 https://www.raspberrypi.org/products/raspberry-pi-3-model-b/ this message in the control flow (Listing 1). If there were many, and if we wanted to collect only one of the receivers in the control flow, we could have used the contextual menu in the class browser to specify this receiver (Figure 6).

Once it has been defined, the collector starts collecting objects. It can be accessed through a local variable if it has been stored by the user, or through the Collectors interface #allCollectors. We can then specify a collect action, which will print the sensor reads in the console: collector onCollectDo:

[:object :collector| Transcript crShow: object printString]

Instead of logging, we could apply more complex operations on the collected objects (e.g. behavioral adaptation). In that case, we should also specify a release action which will ensure that the released objects are not affected by the collector anymore. However that is not the case in this example.

Collecting only for the temperature sensor. Once specified, the collect action logs every object at collection time. We can scope the collector and its action to the temperature sensor object, which is the sole instance of the TemperatureSensor class. Once scoped, the collector will only collect and log sensor reads instantiated by this object: collector scopeToObject: temperatureSensor Note that finding this temperatureSensor object can be subject to the same problems from Section 2.2. We are able to find it using the remote inspector of TelePharo, by inspecting the states of the main running application (i.e. the sole instance of the IotApp class).

Scoping the collection to a specific condition. All temperature sensor readings are not that interesting, as most of them are accurate. We are interested in readings with erratic values, to log their full state and to understand what is wrong. Thus, we specify a condition for object collection. Only sensor readings with values outside of the reading bounds will be collected:

DISCUSSION

We successfully used Collectors in a simple use-case of debugging to log the state of specific objects. Collectors were remotely defined in the IOT App from the developer's computer. Objects of interest were collected at runtime on the IOT object, on which was running the app. Condition checks and collect time actions (i.e. the logging) were also performed on the IOT object. The resulting traces were dynamically displayed on the developer's computer when objects were collected. Only very specific objects were collected and printed.

In regards to the original use-case [START_REF] Marra | Debugging Cyber-Physical Systems with Pharo[END_REF], Collectors provided dynamic and non-intrusive instrumentations to observe the runtime. We use remote debuggers as a support to remotely control Collectors and get feedback from the collected objects. We thus avoid direct code changes injection, and give the developer flexibility on how to interact with objects of interest. Specifically, collectors can be dynamically scoped to the control flow of specific objects.

Collection can be subject to conditions, and the developer can perform custom actions at collect time. Furthermore, a collector can be released when it is no longer needed. This ensures that the original program stops collecting objects, and thus stops performing actions at collect time.

The logging demonstration in this paper is only meant to keep the focus on the Collectors main purpose. There could be many applications, from logging and debugging to behavior adaptation of objects. For example, we successfully reproduced the same experiment with Collectors but with an adaptation mechanism [START_REF] Costiou | Lub: A pattern for fine grained behavior adaptation at runtime[END_REF]. Collectors provided objects to the adaptation mechanism, which applied per-instance logging behavior adaptation to them. In a way, Collectors were a mean of scoping the adaptations to a restricted and dynamic set of objects. In that case, Collectors could be considered as an explicit selection mechanism for Group-Based Adaptation [START_REF] Rein | Group-Based Behavior Adaptation Mechanisms in Object-Oriented Systems[END_REF].

However, the current implementation and model are limited to one thread. Collectors are also inefficient for methods on the stack with running loops. For now, a collector will only be activated once the loop finished and once the method is re-executed. How Collectors affect performances remains to be studied, and how the solution can scale in bigger programs has yet to be evaluated. There are also no fail safe mechanism if an error occurs in the collect action. For now it is the responsibility of the developer to handle errors. However, error handling does not prevent the developer to jeopardize the state of the collected objects. It is not sufficient to guarantee that objects are preserved throughout the developer's actions.

The object focus of Collectors also has the drawback that everything is expressed from and for the object. Other solutions, for example aspects [START_REF] Kiczales | Aspect-oriented programming[END_REF], can provide access to a larger context of execution. That particular point is part of a future extension of the Collectors.

RELATED WORK

In the following, we discuss the possibilities of acquiring objects through runtime modifications, through the control flow or through direct object references.

One important aspect is the ability to inject removable code instrumentations without manually modifying the code. For Collectors, this comes from the implementation layer, Reflectivity [START_REF] Nierstrasz | Model-centric, context-aware software adaptation[END_REF]. This is why we also discuss related work from an implementation perspective.

Easing the chase for objects through code update. The example code we showed in Section 2.1 could be improved in a way that it could solve part of or all of the problems we described.

It could be done through refactoring [START_REF] Fowler | Refactoring: improving the design of existing code[END_REF], but it would change the structure of the program -which may not be desirable or even possible at runtime. Furthermore, it might not solve everything in larger, more complex programs. Intrusive techniques, like dynamic software update [START_REF] Würthinger | Unrestricted and safe dynamic code evolution for Java[END_REF], may also change the program's structure and make it difficult to revert instrumentations.

Control Flow Object Collection. Selecting objects from the control flow means that somehow code has to be dynamically injected to get references. This code would also need to be later removed, when the target objects are no longer of interest. Such technique is used for example in Context Oriented Programming [START_REF] Hirschfeld | Context-oriented programming[END_REF] or in Group-Based Adaptation [START_REF] Rein | Group-Based Behavior Adaptation Mechanisms in Object-Oriented Systems[END_REF].

Objects can be explicitly selected by manually inserting code, if the developer already knows in which part of the code these objects can be found. They can also be implicitly selected, when they automatically become part of an active context. Because Collectors are based on Reflectivity [START_REF] Nierstrasz | Model-centric, context-aware software adaptation[END_REF], they do not require manual insertion or removing of instrumentation. Instead, object collection is explicit and the developer has to define it in the control flow -although it is implemented as hidden instrumentations of the AST.

Aspects [START_REF] Kiczales | Aspect-oriented programming[END_REF] can provide access to objects at key points in the control flow and trigger method calls on them. However and as far as we know, Aspects mainly provide code as the main interacting abstraction. By themselves, Aspects are a solution on top of which the Collectors could be implemented.

Edit Transactions [START_REF] Mattis | Edit Transactions: Dynamically Scoped Change Sets for Controlled Updates in Live Programming[END_REF] embeds live modifications into change sets that can be dynamically turned on and off. One could manually design object selection in the control flow of the program, and (de)activate them when needed. It could provide a dynamic object collection at runtime, with live feedback and view on the collected objects. The code instrumentation to gather the objects has to be manually written into the control flown and the developer always sees the instrumentations to collect objects as source code modifications. It is another way of seeing objects from a running program, from a code-centric oriented perspective.

Object references. Remote debuggers can provide entry points in programs, e.g. to halt the system and open a view on the current stack from which the user can search for references. It has the disadvantage to stop the execution of the inspected thread. Pharo [START_REF] Andrew P Black | Pharo by example[END_REF] provides Telepharo3 , that has a remote debugger, a remote code browser and a remote scripting interface. With such dynamic tool, it is possible to remotely query for all instances of a given class, and then try to find objects of interest.

However it is highly unpractical, as there are no guarantee about the number of objects it would return. It could be impossible to find a particular object among thousands of references. It could also miss objects or provide false positives because of ducktyping, if variables in the code do not always refer to objects of the same types [START_REF] Milojković | It's duck (typing) season![END_REF]. Also, this technique would not allow to get reliable references on temporaries variables or on objects with a very short lifespan.

Listing references of objects of interest can be an interesting alternative. For example the Chisel framework [START_REF] Keeney | Completely unanticipated dynamic adaptation of software[END_REF] provides an object store that can reference objects of interest by name. These objects must be manually named, and necessitate the user to profile the application to identify and name them. This kind of solution is also particularly resource consuming, as every object in the program must be logged in a database for inspection by the user.

Implicit selection mechanisms in Group-Based Adaptation [13] can automatically find and manage collections of objects satisfying specific conditions. Objects can enter or leave a group, depending on selection criteria. For example Reactive Object Queries [START_REF] Lehmann | Reactive Object Queries[END_REF] allow the developer to automatically create and maintain views of objects. Objects are selected through queries. Depending on its state an object can enter or leave a view. The semantics of Collectors is different because they do not select subsets of existing objects, but try to collect all the marked entities in the control flow.

Although Collectors can evaluate conditions for object collection, these conditions are never reevaluated for collected objects. Furthermore, Collectors explicitly target objects from the control flow instead of querying potential objects from the entire object space.

CONCLUSION

In this paper, we described three problems of finding objects at runtime, namely:

(1) The limited lifespan object problem, (2) The "anonymous" object problem, (3) The multiple instances problem.

To address these problems we presented the Collectors. They allow to target objects of interest at runtime from variables in the source code. These objects are gathered and presented to the developer for interaction. We presented the Collectors API and tools, which provide object-centric views of variables from the control flow.

We experimented Collectors on a use-case of remote debugging in an IOT application. We used the Collectors on a runtime example featuring the aforementioned problems. We were able to gather objects by dynamically targeting them in the source code, and to log them into a console. This would have been difficult without a possibility to collect these objects at runtime.

We concluded by a discussion on Collectors and their application. We drafted future works that should be done to evaluate further the solution. We plan a more thorough investigation of the Collectors impact on the overall performance of a runtime. We also plan to investigate how to collect objects in multi-threaded applications. Finally, and in regards to the studied related work, it would be interesting to combine Collectors with features from other solutions. For example, access to execution context could be added to the Collectors specifications, or a finer management of the collected objects collections.

Figure 1 :

 1 Figure 1: Collecting objects referenced by a temporary variable in a method.

Figure 2 :

 2 Figure 2: Collecting objects referenced by an instance variable.

Figure 3 :

 3 Figure 3: Collecting objects to which the #add: message is sent in a method.

Figure 4 :

 4 Figure 4: Collecting objects to which the #add: message is sent at a specific position in the code of a method.

  collectors := Collector allCollectors. "Get all collectors" collector := collectors first. "Access first collector" objects := collector collectedObjects. "Collected objects" collector release "Release collector" Scoping a collector. A collector can be scoped to a single object, if the developer can provide a reference to this object. In that case, object collection is active for the specified object only: collector scopeToObject: anObject. Seeking and Finding Objects at Runtime with Collectors <Programming'18> Companion, April 9-12, 2018, Nice, France

  collector onCollectDo: aBlock. collector onReleaseDo: aBlock As an example, we can configure a collector to print each collected object in the Transcript console of Pharo: collector onCollectDo: [:collectedObject :collector| Transcript crShow: collectedObject printString].

Figure 5 :Figure 6 :Figure 7 :

 567 Figure 5: The Collectors browser: (A) collectors list, (B) collectors specification, (C) actions on collection and release of objects, (D) condition for object collection and (E) the entities to which object collection is scoped

Figure 8 :

 8 Figure 8: The Sensor Monitoring App

  collector condition: [:object| object value > 1023 or:[object value < 0]]

https://kloum.io/costiou/collectors

https://github.com/dionisiydk/TelePharo

ACKNOWLEDGMENTS

We would like to thanks the anonymous reviewers and the participants of the PX/18 Writer's Workshop for their very interesting and constructive discussion and feedback.