# Version 0.1
# Use CPLEX solver
option solver cplexamp;
option show_stats 1;
option times;

# ---------------
# Data flow graph
# ---------------

# DFG nodes
set G;

# DFG edges
set EG within (G cross G);

# Operator of DFG nodes
param OPG {G} default 0;

# Out-degree of DFG nodes
param ODG {G} default 0; 

# --------
# Patterns
# --------

# Pattern indexes
set P_prime; # patterns with edges
set P_second; # patterns without edges
set P := P_prime union P_second; 

param n integer > 0;  # Dummy nodes for parameters instances
set PN := 0 .. n - 1; # Generic pattern nodes

# Patterns
set B {P} within PN;
# Pattern edges
set EP {P_prime} within (PN cross PN);
# Operator of patterns
param OPP {P,PN};
# Out-degree of patterns
param ODP {P,PN} default 0;
# Latencies
param L {P};

#----------
# Resources
#----------

# Functional units
set F;
# Maximum FUs
param M {F} integer >0;
# Resource mapping p <-> FU
param U {P,F} binary default 0;

#------------
# Issue width
#------------

# Issue width (omega)
param W integer > 0;
# Number of registers
param R integer > 0;

# ------------------
# Solution variables
# ------------------

var w {EG,P_prime,(PN cross PN)} binary default 0;
var x {EG} binary default 0;

# Maximum time
param max_t integer > 0;
set T := 0 .. max_t;
var c {G,P,PN,T} binary default 0;
var exec_time integer >= 0;

# Records which patterns (instances) are selected, at which time
var s {P_prime,T} binary default 0;

# Records if a node i requires a register at time t
var r {G,T} binary default 0;

# ---------------------------------------------------------------------------

# -----------------
# Optimization goal
# -----------------

minimize Test:
	exec_time;

# Minimize the number of steps 
subject to MinClockCycle {i in G, p in P, k in B[p], t in T}:
	 c[i,p,k,t] * (t + L[p]) <= exec_time;

# ---------------------
# Instruction selection
# ---------------------

# Each node is covered by at most one pattern
subject to NodeCoverage {i in G}:
	sum{p in P} sum{k in B[p]} sum{t in T} c[i,p,k,t] = 1;

# Record which patterns have been selected at time t
subject to Selected {p in P_prime, t in T}:
	sum{i in G} sum{k in B[p]} c[i,p,k,t] = s[p,t] * card{B[p]};

# Unicity: each pattern node corresponds to a unique DFG node (if p selected)
subject to Unicity {p in P_prime, k in B[p]}:
	sum{i in G} sum{t in T} c[i,p,k,t] = sum{t in T} s[p,t];

# For each selected pattern, assure that all pattern edges matches DFG edges
subject to EdgeCoverage {p in P_prime}:
	sum{(i,j) in EG} sum{(k,l) in EP[p]} w[i,j,p,k,l] 
	  = card{EP[p]} * sum{t in T} s[p,t];

# For each pattern edge, assure that DFG nodes are matched to pattern nodes
subject to WithinPattern {(i,j) in EG, p in P_prime, (k,l) in EP[p]}:
	2 * w[i,j,p,k,l] <= sum{t in T}(c[i,p,k,t] + c[j,p,l,t]);

# Only one instance of a pattern might be selected at some time t
subject to MaxOneInstance {p in P_prime}:
	sum{t in T} s[p,t] <= 1;

# Operator of DFG and pattern nodes must match
subject to OperatorEqual {i in G, p in P, k in B[p], t in T}:
	c[i,p,k,t] * (OPG[i] - OPP[p,k]) = 0;

# The out-degree of DFG and pattern nodes must match
subject to OutDegree {p in P_prime, (i,j) in EG, (k,l) in EP[p]}:
	w[i,j,p,k,l] * (ODG[i] - ODP[p,k]) = 0;


# -------------------
# Register allocation
# -------------------

# Register pressure
# Set value to register r[i,t] if there are at least one edge active at time t
subject to SetReg {t in T, i in G}:
	sum{tt in 0..t} sum{(i,j) in EG} sum{p in P} (
	  sum{k in B[p]} c[i,p,k,tt] - sum{l in B[p]} c[j,p,l,tt]
	) <= r[i,t] * 1000;

# If there are no active edges at time t left, set r[i,t] to zero
subject to ZeroIfNoActiveEdges {t in T, i in G}:
	sum{tt in 0..t} sum{(i,j) in EG} sum{p in P} (
	  sum{k in B[p]} c[i,p,k,tt] - sum{l in B[p]} c[j,p,l,tt]
	) >= r[i,t];

# Check that the number of registers is not exceeded at any time
subject to RegPressure {t in T}:
	sum{i in G} r[i,t] <= R;

# ----------------------
# Instruction scheduling
# ----------------------

# Precedence constraints for patterns-to (pattern or singleton)
subject to PrecedencePT {p in P_prime, (i,j) in EG, t in T}:
	sum{k in B[p]} c[i,p,k,t] + 
	sum{q in P: q != p}
          sum{tt in 0 .. t + L[p] - 1: tt <= max_t}
            sum{k in B[q]} c[j,q,k,tt] <= 1;

# Precedence constraints for singleton-to (pattern or singleton)
subject to PrecedenceST {p in P_second, (i,j) in EG, t in T}:
	sum{k in B[p]} c[i,p,k,t] + 
	sum{q in P} sum{tt in 0 .. t + L[p] - 1: tt <= max_t}
            sum{k in B[q]} c[j,q,k,tt] <= 1;

# -------------------
# Resource allocation
# -------------------

# At each scheduling step we should not exceed the number of resources
subject to Resources {t in T, f in F}:
	sum{p in P_prime : U[p,f] = 1} s[p,t] 
	+ sum{p in P_second : U[p,f] = 1} 
            sum{i in G} sum{k in B[p]} c[i,p,k,t] <= M[f];

# At each time slot, we should not exceed the issue width w
subject to IssueWidth {t in T}:
	sum{p in P_prime} s[p,t]
	+ sum{p in P_second} sum{i in G} sum{k in B[p]} c[i,p,k,t] <= W;

# ---------------------------------------------------------------------------

# ----------------
# Check statements
# ----------------

# Each pattern should be associated with some functional unit
check {p in P}:
	sum{f in F} U[p,f] > 0;