// ABRO - the "hello world" for SSMs
// Example from Charles André, Semantics of SyncCharts,
// ISRN I3S/RR-2003-24-FR, April 2003, Figure 5-12
//
// rvh, 17 mar 2009

#include "scl.h"


// ======================================
// Program-specific definitions

// Signals
typedef enum {_A, _B, _O1, _O2} signaltype;
int A, B, O1, O2;
const char *s2signame[] = {"A", "B", "O1", "O2"};

#define _SC_ID_MAX  6           // Highest thread id in use
#define _SC_SIG_MAX 4           // Highest signal id in use

#define RUNMAX  2               // # of runs to execute
#define TICKMAX 3               // # of ticks to execute

#include "sc.h"

// Try out whether we can avoud conditional jumps
// However, with -O3, the following does not seem to make a difference
//#define _merge(flag, new, old) flag ? new : old
//#define _merge2(flag, new, old) (~!flag & new) | (~flag & old)

// For handling booleans, we use & and | instead of && and ||, to
// avoid conditional jumps introduced by "short circuit" evaluation of && and ||.
// The following combination of definitions yields the best results with
// gcc -O3 (64 bit).
// However, for inexplicable reasons _mergeFalse2 would yield better results
// when applied to both O1_entry and O2_entry (60 instead of 63 instructions).
#define _mergeTrue(flag, old) flag | old
//#define _mergeTrue2(flag, old) flag ? true : old

#define _mergeFalse(flag, old) (!flag) & old
//#define _mergeFalse(flag, old) _mergeFalse2(flag, old)
//#define _mergeFalse2(flag, old) flag ? false : old
//#define _mergeFalse2(flag, old) _mergeFalse(flag, old)


// Inputs for RUNMAX runs of TICKMAX ticks
sigset inputs[RUNMAX][TICKMAX] =
  {{u2b(_A), 0, u2b(_B)},
   {0, u2b(_A), 0}};
//{{0, 0, 0,}, {0, 0, 0,}};

// Expected outputs
sigset outputs[RUNMAX][TICKMAX] =
  {{u2b(_A)|u2b(_B)|u2b(_O1), u2b(_O1), u2b(_B)|u2b(_O2)},
   {0, u2b(_A)|u2b(_B)|u2b(_O2), u2b(_O2)}};
//{{0, 0, 0,}, {0, 0, 0,}};

// May want to exclude non-tick functions, to measure object code size for tick function
#ifndef _SC_ONLY_TICK_FUNCTION
void getInputs(int runCnt, int tickCnt)
{
  signals = inputs[runCnt][tickCnt];

  // Variables are persistent - therefore must initialize them
  // at every run
  if (tickCnt==0) {
    O1 = false;
    O2 = false;
  }
}

// Set reference outputs and check valued signals, if there are any.
// Return 1 unless valued signal outputs are wrong.
// No valued signals here, therefore always return 1.
int checkOutputs(int runCnt, int tickCnt, _setPartType *tickOutputs)
{
  *tickOutputs = outputs[runCnt][tickCnt];
  return 1;
}

// No valued signals to print
void printVal(int id)
{
}

// The following functions serve to make input/output signal traces
// available for variables

// Copy input signals to variables
void signals2vars() {
  A = _sigContains(signals,_A);
  B = _sigContains(signals,_B);
}

// Copy output variables to signals
void vars2signals() {
  if (A) EMIT(_A);
  if (B) EMIT(_B);
  if (O1) EMIT(_O1);
  if (O2) EMIT(_O2);
}
#endif

#define UNDEFINED -1

// Tick function
/* SSA-version inspired by Esterel's circuit semantics [1]
 *
 * [1] Gerard Berry, "The Constructive Semantics of Pure Esterel, Draft Version 3," July 1999
 * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.46.2076&rep=rep1&type=pdf
 *
 * The following is written in a variant of SSA (Static Single
 * Assignment).
 *
 * 1) Variables that are written to multiple times, possibly including
 * input assignments, are split up into distinct copies for each
 * write.
 *
 * 2) Writes are "merged", depending on their sequential order of
 * execution.
 *
 * Notes: (i) This merging must only be done for variables that can be
 * written to in the same tick. At least for an initial
 * implementation, we may conservatively assume that all writes can
 * occur in the same tick. (ii) Sequential constructiveness requires
 * that concurrent writes must be confluent (otherwise the program
 * would have to be rejected). Thus we merge concurrent writes in
 * arbitrary sequential order. (iii) As a result, we have a total
 * order for all writes that can be executed in the same tick.
 *
 * 3) To determine which writes are "active", ie, whether control
 * reaches them in the current tick, each basic block is augmented
 * with an "activation flag" that is set to true when the basic block
 * is executed. This roughly corresponds to the guards in guarded
 * command (see eg. Schneider et al.).
 *
 * 4) Reads must pick the one "right" merged write.
 * Sketch for an approach: consider all potentially relevant writes
 * that may take place in the same tick (using write-read
 * dependencies), pick from those writes the "latest merge", according
 * to aforementioned total ordering of the writes. If there can be no
 * concurrent write, then use pre-Value.
 * 
 * For HW synthesis, the code can be translated directly to a net
 * list. Only registers need special treatment.
 *
 * For SW synthesis, one might have to reorder assignments such that
 * writes occur before reads. In this example, this is not necessary,
 * as the only concurrent write-read dependence, on B, orders a
 * statement of the first thread before another statement of the
 * second thread, which already corresponds to the ordering of the
 * code.
 *
 * Both HW and SW synthesis might reject programs, when they do not
 * permit a static schedule. For example, with this approach, HW
 * synthesis does not permit "instantenous loops", which can be
 * handled naturally in SW; conversely, SW synthesis might reject some
 * programs that still result in deterministic circuits, such as the
 * Token Ring Arbiter. However, the intersection of the SW- or
 * HW-synthesizable subsets should still be quite large. Eg, it
 * encompasses all of what was acceptable for Esterel, plus many more
 * programs that can be handled by permitting sequential
 * assignments. This includes the following example, which can be
 * synthesized into both HW and SW, but would be rejected by Esterel
 * Studio or SCADE.
 */
int tick()
{
  // Activation flags for basic blocks
  //
  // On Naming:
  // The flags are not just numbered through, but have names that
  // should give an idea what node/basic block they correspond to.
  // "entry" and "exit" are the basic blocks corresponding to the
  // top-level entry and exit nodes.
  //
  // If there is no obvious name for a basic block, use just
  // _go<counter>_<thread path>, as done for _go0_HandleA.
  //
  // Note that these might be computed even more efficiently using a
  // Program Dependence Graph (PDG), which could expose further parallelism.
  // However, we for now make do with a simpler, locally computed scheme.
  bool _entry, _go0_HandleA, _surf_HandleA_WaitA, _exit_HandleA, _surf_HandleB_WaitB, _exit_HandleB, _exit;

  // Registered activation flags, for basic blocks that end in pause statements
  // "true" indicates an active pause statement; initially pause statements are inactive
  static bool _depth_HandleA_WaitA = false, _depth_HandleB_WaitB = false;

  // Flags indicating that a region is empty (inactive),
  // ie, neither just started nor any active pause
  bool _empty_HandleA, _empty_HandleB;

  // Values; multiple instances of O1, O2, and (input) B
  // On Naming:
  // Use suffix derived from activation flags of the enclosing basic block.
  // If there are multiple assignments to the same variable within on basic block, 
  // use increasing counter, starting at 0, for the assignments - except for the last
  // assignment, as that is the one visible outside of the basic block.
  // The assignments with a counter suffix are only visible within the basic block.
  // Eg, assume we are in basic block "entry":
  //   X = 0; Y = X; X = 1
  // becomes
  //   X_entry0 = 0; Y_entry = X_entry0; X_entry = 1
  bool O1_entry, O1_exit_HandleA, O1_exit_HandleB, O1_exit, O2_entry, O2_exit, B_exit_HandleA;

  // Registered values of non-input variables
  // For SW, one would not need to make these explicit, one might instead just use O1 and O2
  // Note: O1 and O2 are declared globally, to make them visible outside of tick function
  static bool _preO1 = UNDEFINED, _preO2 = UNDEFINED;

  //tickstart(2);
  _signals2vars

  // RESET() initializes _notInitial = 0;
  _entry = !_notInitial;   // _entry indicates initial tick

  //if (!_notInitial)
  //  _notInitial = _notInitialDetect;
  //Replaced with code that avoids jump:
  _notInitial |= _notInitialDetect;

  // O1 = false;

  // Observations:
  // 1) The above assignment is only effective when _entry holds
  // 2) If the assignment is effective, it overrides _preO1
  // Thus, we perform a "sequential merge" below.
  // This is somewhat similar to a phi node, except that the merged assignments
  // do not have to come from separate control paths.
  O1_entry = _mergeFalse(_entry, _preO1);

  // O2 = false;
  O2_entry = _mergeFalse(_entry, _preO2);

  //fork1(HandleB, 1) {
  //HandleA:

  // Merge paths before reaching conditional
  //_go0_HandleA = _entry || _depth_HandleA_WaitA;
  _go0_HandleA = _entry | _depth_HandleA_WaitA;

  //  if (!A) {

  //  pause;  // WaitA
  // Replace this pause with a register "_surf_HandleA_WaitA" that indicates an active pause
  _surf_HandleA_WaitA = _go0_HandleA & !A;  // _depth_HandleA_WaitA is registered value

  //  goto HandleA;
  //}

  _exit_HandleA = _go0_HandleA & A;

  // The input B constitutes a "0th" copy of B that is always present
  // Therefore, must create copy for following write to B
  // B = true;
  // Possible optimization for SW: replace assignment to B_exit_HandleA by assignment
  // to just B, as it is the final value of B
  B_exit_HandleA = _mergeTrue(_exit_HandleA, B);

  // O1 = true;
  O1_exit_HandleA = _mergeTrue(_exit_HandleA, O1_entry);

  // Compute "output pins" of thread HandleA
  // This is analogous to the LEM/REM pins [1, Fig. 11.1]
  _empty_HandleA = !(_entry | _surf_HandleA_WaitA);   // Dead thread - neither just started nor any active register

  //} par {
  //  HandleB:
  //  pause;

  // Observation, regarding the read of B:
  // Possible writes to B are the input (called just "B") and B_exit_HandleA.
  // As B_exit_HandleA is a "sequential successor" of B, the "merge" of these two is
  // already computed in B_exit_HandleA
  _surf_HandleB_WaitB = _entry | (_depth_HandleB_WaitB & !B_exit_HandleA);  // Set register _surf_HandleB_WaitB

  //  if (!B) {
  //    goto HandleB;
  //  }
  _exit_HandleB = _depth_HandleB_WaitB & B_exit_HandleA;

  //  O1 = true;

  // Observation:
  // The assignments to O1 that correspond to O1_exit_HandleA and O1_exit_HandleB
  // are concurrent, i.e., not sequential, but confluent.
  // Thus we (arbitrarily) merge them by first computing O1_exit_HandleA, and then
  // possibly overwriting this with "true" in the assignment to
  // O1_exit_HandleB.
  // We could also have reversed this order.
  O1_exit_HandleB = _mergeTrue(_exit_HandleB, O1_exit_HandleA);

  // Compute "output pins" of thread HandleB
  _empty_HandleB = !(_entry | _surf_HandleB_WaitB);

  //} join1(2);
  // This corresponds to output K0 of Sychronizer circuit [1, Fig. 11.10]
  // If this were not the basic block corresponding to the top-level exit node,
  // we would have called this "_join_WaitAB"
  _exit = (_exit_HandleA | _exit_HandleB)  // At least one thread must have just terminated
    & (_exit_HandleA | _empty_HandleA)   // HandleA has terminated or was already dead
    & (_exit_HandleB | _empty_HandleB);  // HandleB has terminated or was already dead

  // O1 = false;
  // O1_exit is sequentially after O1_exit_HandleA and O1_exit_HandleB.
  // As stated above, O1_exit_HandleA and O1_exit_HandleB are concurrent, but are merged in
  // O1_exit_HandleB. Thus we here merge with O1_exit_HandleB.
  O1_exit = _mergeFalse(_exit, O1_exit_HandleB);

  //O2 = true;
  O2_exit = _mergeTrue(_exit, O2_entry);

  // Compute output values.
  // This is where the nature of sequentiality becomes apparent:
  // we always use the "last" write to a variable.
  // For HW synthesis, would have to replace these by A_out, B_out, O1_out, O2_out
  //A = A;       // Input A is not overwritten
  B = B_exit_HandleA;
  O1 = O1_exit;
  O2 = O2_exit;

  // THE FOLLOWING CODE FOR SW SYNTHESIS ONLY:

  // Emulate registers by copying them for next tick
  _depth_HandleA_WaitA = _surf_HandleA_WaitA;
  _depth_HandleB_WaitB = _surf_HandleB_WaitB;
  _preO1 = O1;
  _preO2 = O2;

  //tickreturn();
  _vars2signals

  return !_exit;  // Return true iff automaton continues running
}

// Local Variables:
// compile-command: "make ABRO; ABRO"
// End:
