///  LSU EE 4755 -- Fall 2019 -- Digital Design / HDL
//
/// Verilog Notes -- Synthesis of Comb. Behavioral Code

/// Under Construction


/// Contents
 //
 /// Inference of Combinational Behavioral Code
 /// Optimization of Inferred Combinational Behavioral Code

/// References

// :SV12: IEEE 1800-2012 -- The SystemVerilog Standard
// :SV17: IEEE 1800-2017 -- The SystemVerilog Standard
//        https://ieeexplore.ieee.org/document/8299595/
//        This is for those already familiar with Verilog.
//
// :BV3:  Brown & Vranesic, Fundamentals of Digital Logic with Verilog, 3rd Ed.
//        The text used in LSU EE 2740.
//
//  Genus HDL Modeling Guide -- Access from Within lsu.edu Only.
//        https://www.ece.lsu.edu/v/s/genus_hdlmod.pdf
//


//////////////////////////////////////////////////////////////////////////////
/// Inference of Combinational Behavioral Code

 /// Restrictions on Code
 //
 //  Must be in an always or always_comb block.
 //
 //  For always, sensitivity list must contain all RHS live-in variables.
 //
 //  A variable is either always assigned or never assigned.
 //
 //  A variable can be assigned in at most one block.

 /// Types of Code
 //
 //  -- Assignments. Re-assignments.
 //
 //  -- if / else blocks.  Complete, incomplete.
 //
 //  -- case blocks
 //
 //  -- Loops



 /// Simple Cases:  Variable assigned once.  No control flow statements.


module pie_00( output uwire x, y,  input uwire a, b, c );

   assign x = ~ ( a ^ b );
   assign y = x & c | b;

endmodule

module pie_01( output logic x, y,  input uwire a, b, c );

   always_comb
     begin
        x = ~ ( a ^ b );
        y = x & c | b;
     end
endmodule

// Image:300pt: pie2.plain.svg



 /// Multiple Assignments
//
//  A var cannot be assigned in more than one block.
//  A var can be assigned any number of times in a block.
//
//  Each assignment creates a new wire.
//


// :Example:
//
// The only difference between the two modules below is the name of
// the connection between the XOR and NOT gates. In pie_02 that
// connection is x, in pie_03 that connection is aeb.

module pie_02( output var logic x, y,  input uwire logic a, b, c );

   always_comb
     begin
        x = a ^ b;     // Line 1.
        x = ~ x;       // Line 2.
        y = x & c | b; // Line 3.
     end

endmodule

module pie_03( output logic x, y,  input uwire a, b, c );

   logic aeb;

   always_comb
     begin
        aeb = a ^ b;
        x = ~ aeb;
        y = x & c | b;
     end

endmodule


module mult_by_11_version_00
  ( output logic [15:0] prod,
    input uwire [11:0] a );

   always_comb begin
      prod = a;              // L1
      prod = prod + a * 2;   // L2
      prod = prod + a * 8;   // L3

   end

endmodule

// Image:400pt:l045-mult-by-11.plain.svg;


module mult_version_00
  ( output logic [15:0] prod,
    input uwire [11:0] a,
    input uwire [2:0] b );

   logic  [15:0] pp;
   always_comb begin

      prod = 0;
      pp = b[0] ? a << 0 : 0;  // Line pp0
      prod = prod + pp;        // Line s0
      pp = b[1] ? a << 1 : 0;
      prod = prod + pp;
      pp = b[2] ? a << 2 : 0;
      prod = prod + pp;

   end

endmodule

module mult_version_01
  ( output logic [15:0] prod,
    input uwire [11:0] a,
    input uwire [2:0] b );

   always_comb begin

      prod =  b[0] ? a << 0 : 0;
      prod += b[1] ? a << 1 : 0;
      prod += b[2] ? a << 2 : 0;

   end

endmodule

//////////////////////////////////////////////////////////////////////////////
/// Inference of if Statements
//
//
// Case: if ( COND ) begin IFPART end else begin ELSEPART end
//
//  - Find all variables assigned in both IFPART and ELSEPART ..
//    .. let VARS denote these variables.
//
//  - For each vee in VARS:
//    - Synthesize a multiplexor.
//    - Label the two inputs and output vee.  (Three signals, same name.)
//    - The select input is connected to COND.

// Consider: if ( COND ) IFPART else if ( COND2 ) IFPART2 else ELSEPART
//
//


// :Example:
//
// A simple module with an if/else statement and an assignment.
//
module addborc
 ( output logic [15:0] x,
   input uwire [15:0] a, b, c,
   input uwire d );

   logic [15:0] t;

   always_comb begin
      if ( d ) t = b; else t = c;
      x = a + t;
   end
endmodule

// Inferred Hardware, with labels
// Image:210pt: ill-borc-label.plain.svg

// Inferred Hardware, without labels
// Image:200pt: borc.plain.svg



// :Example:
//
// A module with both an if/else and an if.
//
module addborcb
   ( output logic [15:0] x,
     input uwire [15:0] a, b, c,
     input uwire d );

   logic [15:0] t;

   always_comb begin
      if ( d ) t = b; else t = c;   // L1
      if ( a < 8 ) t = t + 12;      // L2
      x = a + t;                    // L3
   end
endmodule

// Image:400pt: behavifif.plain.svg



module mult_version_02
  #( logic [2:0] b = 3 )
   ( output logic [15:0] prod,
     input uwire [11:0] a );

   always_comb begin

      prod =  b[0] ? a << 0 : 0;
      prod += b[1] ? a << 1 : 0;
      prod += b[2] ? a << 2 : 0;

   end

endmodule


module mult_version_03
  ( output logic [15:0] prod,
    input uwire [11:0] a,
    input uwire [2:0] b );

   always_comb begin
      if ( b[0] ) prod = a << 0; else prod = 0;
      if ( b[1] ) prod += a << 1;
      if ( b[2] ) prod += a << 2;
   end

endmodule

module mult_version_03b
  #( int bwidth = 3 )
   ( output logic [15:0] prod,
     input uwire [11:0] a,
     input uwire [bwidth-1:0] b );

   always_comb begin
      if ( b[0] ) prod = a << 0; else prod = 0;
      for ( int i=1; i<bwidth; i++ )
        if ( b[i] ) prod += a << i;
   end

endmodule

module mult_version_04
  #( logic [2:0] b = 1 )
   ( output logic [15:0] prod,
     input uwire [11:0] a );

   always_comb begin
      if ( b[0] ) prod = a << 0; else prod = 0;
      if ( b[1] ) prod += a << 1;
      if ( b[2] ) prod += a << 2;
   end

endmodule

module mult_version_05
   ( output logic [15:0] prod,
     input uwire [11:0] a );

   mult_version_03 mm(prod,a,3'd3);

endmodule


//////////////////////////////////////////////////////////////////////////////
/// Inference of Loops
//
 /// Loop Statements
//
//   :Syntax:   for ( TYPE I = INIT;  TEST;  INCR ) BODY;
//
//   :Example:  for ( int i=0;  i<3;  i++ ) a[i] = b[2-i];
//
//   Synthesizability Rule
//
//   - Number of iterations must be known at elaboration time ..
//     .. including early exits (breaks).
//
//   Inferred Hardware
//
//     Let n denote the number of iterations.
//
//     Make n copies of the loop body.
//
//     In each copy replace I (the iteration variable) with its
//       value at that iteration.


// :Example:
//
// Examples of loops which are and are not synthesizable.
//
module loop_examples
  #( int sz = 8 )
   ( output logic [sz-1:0] x, y, z,
     input uwire [sz-1:0] a, b, c );

   always_comb begin

      // Good. (Though easier ways to do a bitwise exclusive or.)
      //
      for ( int i=0; i<sz; i++ ) x[i] = a[i] + b[i];

      // Bad: Number of iterations depends on c.
      //
      for ( int i=0;  i < c;  i++ ) y[i] = a[i];
      for ( int i=c;  i < sz; i++ ) y[i] = b[i];

      // Also Bad:
      //
      for ( int i=0;  i < sz;  i++ ) begin
         if ( i == c ) break;  // Not allowed by many synthesis programs.
         y[i] = a[i];
      end

      // Good, though more code than is necessary.
      //
      for ( int i=0;  i < sz;  i++ ) if ( i <  c ) y[i] = a[i];
      for ( int i=0;  i < sz;  i++ ) if ( i >= c ) y[i] = b[i];

      // Good: Fixed Number Of iterations.
      //
      for ( int i=0;  i < sz;  i++ ) y[i] = i < c ? a[i] : b[i];

   end

endmodule


// :Example:
//
// Example of a behavioral combinational logic description of a loop
// in which a loop iteration does not depend on a prior loop
// iteration. (For an example in which iterations do depend on prior
// iterations see the_hard_way, further below.)
//
module loop_example_good
  #( int sz = 8 )
   ( output logic [sz-1:0] z,
     input uwire [sz-1:0] a, b,
     input uwire [sz-1:0] c );

   always_comb for ( int i=0; i<sz; i++ ) z[i] = i < c ? a[i] : b[i];

endmodule

// Inferred Hardware

// Image:40em:ill-loop-ex-good.plain.svg



// :Example:
//
// Example of a behavioral combinational logic description containing
// a loop in which a value produced in one iteration, x, is used the
// subsequent iteration.
//
module the_hard_way
  ( output logic x,
    input uwire [3:0] a, b );

   always_comb
     begin
        x = 0;
        for ( int i=0; i<4; i++ ) x = x | ( a[i] ^ b[i] );
        x = ~x;
     end
endmodule

// Inferred Hardware

// :Image:50em: syn-hard-way.plain.svg





//////////////////////////////////////////////////////////////////////////////
/// Optimization of Inferred Combinational Behavioral Code
//
//  :Def: Optimization [of an HDL Description]
//  The modification of an HDL description (e.g., Verilog code) ..
//  .. that reduces cost, ..
//  .. reduces critical path length (makes it faster), ..
//  .. or meets some other goal or constraint ..
 ///  .. without changing what the HDL description does.
//
 /// Where Optimization is Done
//
//  - Synthesis Programs
//    Usually minimize cost while meeting timing constraints.
//    The result of this optimization is visible in cost and timing reports.
//
//  - HDL Simulation Programs
//    Goal of optimization is to make simulation run faster.
//    The result of this optimization is that ..
//    .. users spend less time waiting for ..
//    .. the "Testbench completed, 0 errors found." message (or whatever).
//
//  Our focus is on synthesis program optimization.
//
 /// When Synthesis Optimization is Done
//
//  Typically, optimization is performed several times.
//
//  - After Inference
//    Sometimes called generic optimization.
//
//  - After Technology Mapping

//
//
//  :Def: Hand Optimization
//  Optimization of an HDL description ..
//  .. performed by EE 4755 students ..
//  .. to demonstrate an understanding of what ..
//  .. synthesis programs are likely to do with a design.
//
 /// Optimization Techniques
//
//   - Constant Propagation and Folding
//   - Logic and arithmetic simplification.
//   - Substitution of equivalent modules.


// :Example:
//
// Optimization of a two-input multiplexor with constant inputs.
//
// Module description (in which inputs are not constant)
//
module mux2(output logic x, input uwire s, a0, a1);

   always_comb if ( s ) x = a1; else x = a0;

endmodule

// Optimization of mux2 when instantiated with one or two constant
// inputs (three cases shown):
//
// Image:40em:ill-mux2-opt.plain.svg



// :Example:
//
// Take sum of selected elements. (Fall 2015 Midterm Exam Problem 2)

module ssum
  #( int n = 3,
     int f = 4,
     int swid = f + $clog2(n) )
   ( output logic [swid-1:0] sum,
     input uwire [n-1:0] mask,
     input uwire [f-1:0] a[n] );

   always_comb begin

      sum = 0;

      for ( int i=0; i<n; i++ )
        if ( mask[i] ) sum += a[i];

   end

endmodule

// Inferred Hardware (Before Optimization):
// Image:400pt: syn-ssum-inf.plain.svg

// After Some Optimization:
// Image:400pt: syn-ssum-opt.plain.svg


// :Example:
//
// Comparison example. Includes a loop and ifs inside ifs.

module compare
  ( output logic gt, lt,  input uwire [2:0] a, b );

   always_comb begin

      gt = 0;
      lt = 0;

      for ( int i=2; i>=0; i-- )

        if ( !gt && !lt ) begin
           if ( a[i] < b[i] ) lt = 1;
           if ( a[i] > b[i] ) gt = 1;
        end
   end

endmodule

// Inferred Hardware:

// :Image:600pt: comp-unopt-2.plain.svg

// Optimization Plan:
// :Image:300pt: comp-opt-1.plain.svg

// After Optimization:
// :Image:400pt: comp-opt-2.plain.svg



// :Example:
//
// Inference of hardware for a module using both constant and
// non-constant index operators. (E.g., v[5], v[idx_min].) (See 2016
// Midterm Exam Problem 3b.)
//
module min_elt
  ( output logic [1:0] idx_min,
    input uwire signed [31:0] v [3] );

   always_comb begin
      idx_min = 0;
      for ( int i=1; i<3; i++ ) if ( v[i] < v[idx_min] ) idx_min = i;
   end

endmodule

// Inferred Hardware, plain and labeled with some Verilog:
// Image:40em:ill-min-elt-i.plain.svg
// Image:41em:ill-min-elt-i-lab.plain.svg

 /// Optimization of min_elt:
//
//  - Eliminate lower-left mux because its select signal is a constant, 0.
//  - Eliminate upper-left mux. (Try drawing a truth table.)
//  - Reduce number of inputs in the lower-right mux from 3 to 2.
//  - Simplify logic for upper-right mux.
//
// Optimized Hardware
// Image:40em:ill-min-elt-o.plain.svg



module pop_c_good
  #(int width = 128, int bits = $clog2(width+1))
   (output logic [bits:1] pop, input [width-1:0] vector);

   always_comb begin

      pop = 0;
      for ( int i=0; i<width; i++ ) pop += vector[i];

   end

endmodule

module pop_c_bad
  #(int width = 128, int bits = $clog2(width+1))
   (output logic [bits:1] pop, input [width-1:0] vector);

   initial begin

      pop = 0;
      for ( int i=0; i<width; i++ ) pop += vector[i];

   end

endmodule

module b_syn_1
  ( output logic [7:0] x,
    input uwire [7:0] a, b,
    input uwire c );

   always_comb begin

      if ( c ) x = a + b;
      else     x = a - b;

   end

endmodule

module b_syn_2
  ( output logic [7:0] x,
    input uwire [7:0] a, b,
    input uwire c );

   always_comb begin

      // Synthesizes to a mux with c as control.
      //
      x = a - b;
      if ( c ) x = a + b;
      //
      // But, bad style because x re-assigned ... makes it harder on humans.

   end

endmodule


module b_syn_bad_1
  ( output logic [7:0] x,
    input uwire [7:0] a, b,
    input uwire c );

   always @* begin

      // Not combinational logic because x not always assigned.
      // Shouldn't synthesize when always_comb used.
      // Will synthesize with "always @*", but will not be combinational.
      //
      if ( c ) x = a + b;
   end

endmodule