//! Scheduling model for program generation

//!

//! HashX uses a simple scheduling model inspired by the Intel Ivy Bridge

//! microarchitecture to choose registers that should be available and

//! avoid stalls.

use crate::program::{Instruction, Opcode};

use crate::register::{RegisterId, NUM_REGISTERS};

/// Scheduling information for each opcode

mod model {

    use crate::program::Opcode;

    /// Number of simulated cycles we run before stopping program generation

    pub(super) const TARGET_CYCLES: usize = 192;

    /// Total number of cycles to store schedule data for

    pub(super) const SCHEDULE_SIZE: usize = TARGET_CYCLES + MAX_LATENCY;

    /// Number of execution ports in our simulated microarchitecture

    pub(super) const NUM_EXECUTION_PORTS: usize = 3;

    /// Identify one or more CPU execution ports

    ///

    /// They are inspired by the Intel Ivy Bridge design and the original HashX

    /// implementation names them P5, P0, and P1.

    ///

    /// We can mostly ignore the names and treat this as an array of three

    /// ports specified in the order that HashX tries to allocate them. The

    /// original HashX implementation explains this allocation order as an

    /// optimistic strategy which assumes P1 will typically be reserved for

    /// multiplication.

    #[derive(Debug, Clone, Copy, Eq, PartialEq)]

    pub(super) struct ExecPorts(pub(super) u8);

    /// Port P5 (first choice) only

    const P5: ExecPorts = ExecPorts(1 << 0);

    /// Port P0 (second choice) only

    const P0: ExecPorts = ExecPorts(1 << 1);

    /// Port P1 (third choice) only

    const P1: ExecPorts = ExecPorts(1 << 2);

    /// Either port P0 or P1

    const P01: ExecPorts = ExecPorts(P0.0 | P1.0);

    /// Either port P0 or P5

    const P05: ExecPorts = ExecPorts(P0.0 | P5.0);

    /// Any of the three ports

    const P015: ExecPorts = ExecPorts(P0.0 | P1.0 | P5.0);

    /// Maximum value of [`instruction_latency_cycles()`] for any Opcode

    const MAX_LATENCY: usize = 4;

    /// Latency for each operation, in cycles

    #[inline(always)]

        }

    /// Break an instruction down into one or two micro-operation port sets.

    #[inline(always)]

        }

    /// Each instruction advances the earliest possible issuing cycle by one

    /// sub-cycle per micro-op.

    #[inline(always)]

        }

}

/// One single execution port

///

/// Formatted to use easily as an array index.

/// It's helpful for this to be a compact data type.

#[derive(Debug, Clone, Copy, Eq, PartialEq)]

struct ExecPortIndex {

    /// Equivalent to a bit position in [`model::ExecPorts`].

    index: u8,

}

/// Overall state for the simulated execution schedule

#[derive(Debug, Default, Clone)]

pub(crate) struct Scheduler {

    /// Current timestamp in the schedule, in sub-cycles

    ///

    /// Sub-cycles advance as code is generated, modeling the time taken to

    /// fetch and decode instructions.

    sub_cycle: SubCycle,

    /// Current timestamp in the schedule, in cycles

    ///

    /// Derived from sub_cycle.

    cycle: Cycle,

    /// State for scheduling execution by fitting micro-ops into execution ports

    exec: ExecSchedule,

    /// State for scheduling register access by keeping track of data latency

    data: DataSchedule,

}

impl Scheduler {

    /// Create a new empty execution schedule at cycle 0

    #[inline(always)]

    /// Stall for one cycle.

    ///

    /// Used when register allocation fails.

    /// Returns `Ok` if we had enough time, or `Err` if we ran out.

    #[inline(always)]

    /// Return the current instruction fetch/decode timestamp in sub-cycles.

    #[inline(always)]

    /// Advance forward in time by some number of sub-cycles.

    ///

    /// Stops just before reaching `Cycle::target()`, where we stop

    /// scheduling new instructions.

    #[inline(always)]

        } else {

        }

    /// Advance time forward by the modeled duration of the instruction fetch

    /// and decode, in sub-cycles.

    ///

    /// Returns Ok if we still have enough time to schedule more, or Err if the

    /// schedule would be full.

    #[inline(always)]

    /// Calculate a timing plan describing the cycle and execution units

    /// on which a particular opcode could run, at the earliest.

    #[inline(always)]

    /// Commit to using a plan returned by [`Self::instruction_plan()`],

    /// for a particular concrete [`Instruction`] instance.

    ///

    /// Marks as busy each execution unit cycle in the plan, and updates the

    /// latency for the [`Instruction`]'s destination register if it has one.

    #[inline(always)]

    /// Look up if a register will be available at or before the indicated cycle.

    #[inline(always)]

    /// Return the overall data latency.

    ///

    /// This is the Cycle at which we expect every register

    /// to reach its final simulated state.

    #[inline(always)]

}

/// Cycle timestamp

///

/// Measured from the beginning of the program, assuming no branches taken.

/// It's useful to be able to store these compactly in register latency arrays.

#[derive(Debug, Default, Clone, Copy, Ord, PartialOrd, Eq, PartialEq)]

pub(crate) struct Cycle(u8);

impl Cycle {

    /// HashX stops generating code once the issue cycle reaches this target.

    #[inline(always)]

    /// Cast this Cycle count to a usize losslessly.

    #[inline(always)]

    /// Add an integer number of cycles, returning Err(()) if we reach the end.

    #[inline(always)]

        } else {

        }

}

/// Sub-cycle timestamp

///

/// Timer for instruction decode, at a finer resolution than the Cycle

/// we use for keeping schedule records. Doesn't need to be compact.

#[derive(Debug, Default, Clone, Copy, Ord, PartialOrd, Eq, PartialEq)]

pub(crate) struct SubCycle(u16);

impl SubCycle {

    /// Number of sub-cycles per cycle

    const PER_CYCLE: u16 = 3;

    /// Maximum value of a sub-cycle counter, based on the schedule size

    const MAX: Self = SubCycle(model::SCHEDULE_SIZE as u16 * Self::PER_CYCLE - 1);

    /// Cast this sub-cycle count into a usize losslessly.

    #[inline(always)]

    /// Convert this sub-cycle into a full Cycle timestamp.

    #[inline(always)]

    /// Advance by an integer number of sub-cycles.

    ///

    /// Returns the new advanced [`SubCycle`], or `Err(())`

    /// if we reach the end of the schedule.

    #[inline(always)]

        } else {

        }

}

/// Busy tracking for one CPU execution port

#[derive(Debug, Default, Clone)]

struct PortSchedule {

    /// Bit array indicating when this port is busy, indexed by Cycle

    busy: SimpleBitArray<

        { (usize::BITS as usize + model::SCHEDULE_SIZE - 1) / (usize::BITS as usize) },

    >,

}

/// Latency tracking for all relevant CPU registers

#[derive(Debug, Default, Clone)]

struct DataSchedule {

    /// Cycle count at which this register is available, indexed by register ID

    latencies: [Cycle; NUM_REGISTERS],

}

impl DataSchedule {

    /// Plan to finish a register write at the indicated cycle

    #[inline(always)]

    /// Look up if a register will be available at or before the indicated cycle.

    #[inline(always)]

    /// Return the overall latency, the [`Cycle`] at which we expect

    /// every register to reach its latest simulated state.

    #[inline(always)]

        }

}

/// Execution schedule for all ports

///

/// This is a scoreboard that keeps track of which CPU units are busy in which

/// cycles, so we can estimate a timestamp at which each instruction will write

/// its result.

#[derive(Debug, Default, Clone)]

struct ExecSchedule {

    /// Execution schedule (busy flags) for each port

    ports: [PortSchedule; model::NUM_EXECUTION_PORTS],

}

impl ExecSchedule {

    /// Calculate the next cycle at which we could schedule one micro-op.

    ///

    /// HashX always searches execution ports in the same order, and it will

    /// look ahead up to the entire length of the schedule before failing.

    #[inline(always)]

        loop {

                {

            }

        }

    /// Mark the schedule busy according to a previously calculated plan.

    #[inline(always)]

    /// Calculate a timing plan describing the cycle and execution units

    /// we could use for scheduling one entire instruction.

    ///

    /// This takes place after the [`Opcode`] has been chosen but before

    /// a full [`Instruction`] can be assembled.

    #[inline(always)]

            // Single-op instructions

            }

            // HashX schedules two-op instructions by searching forward

            // until we find the first cycle where both ports are

            // simultaneously available.

                loop {

                    ) {

                        {

                }

            }

        }

    /// Mark each micro-op in an InstructionPlan as busy in the schedule.

    #[inline(always)]

}

/// Detailed execution schedule for one micro-operation

///

/// Includes the [`Cycle`] it begins on, and the actual

/// execution port it was assigned.

#[derive(Debug, Clone, Copy, Eq, PartialEq)]

struct MicroOpPlan {

    /// The Cycle this operation begins on

    cycle: Cycle,

    /// Index of the execution port it runs on

    port: ExecPortIndex,

}

/// Detailed execution schedule for one instruction

///

/// This is defined as either one or two micro-operations

/// scheduled on the same cycle.

#[derive(Debug, Clone, Copy, Eq, PartialEq)]

pub(crate) struct InstructionPlan {

    /// The Cycle this whole instruction begins on

    cycle: Cycle,

    /// First execution port, always present

    first_port: ExecPortIndex,

    /// Optional second execution port ID, for two-uop instructions

    second_port: Option<ExecPortIndex>,

}

impl InstructionPlan {

    /// Get the Cycle this whole instruction begins on.

    #[inline(always)]

    /// Calculate the cycle this instruction is complete by.

    #[inline(always)]

    /// Convert this `InstructionPlan` back to one or two [`MicroOpPlan`]s.

    #[inline(always)]

    /// Bundle two [`MicroOpPlan`]s into an [`InstructionPlan`],

    /// if they are on matching cycles.

    ///

    /// Returns `Err(())` if the combination is not possible.

    #[inline(always)]

                } else {

                }

            }

        };

}

/// Simple packed bit array implementation

///

/// This could use the `bitvec` crate if we cared to depend on it, but the

/// functionality we need is so tiny let's keep this simple.

#[derive(Debug, Clone, Eq, PartialEq)]

struct SimpleBitArray<const N: usize> {

    /// Array of words to use as a bit vector, in LSB-first order

    inner: [usize; N],

}

impl<const N: usize> Default for SimpleBitArray<N> {

    #[inline(always)]

}

impl<const N: usize> SimpleBitArray<N> {

    /// Set or clear one bit in the array.

    ///

    /// Panics if the index is out of range.

    #[inline(always)]

    /// Get one bit from the array.

    ///

    /// Panics if the index is out of range.

    #[inline(always)]

}