///  LSU EE 4755 -- Fall 2020 -- Digital Design / HDL
//
/// Verilog Notes -- Synthesis of Combinational Logic: Structural

/// Under Construction


/// Contents
//
 // Inference of Expressions
 // Inference of Non-Arithmetic Operators
 // Synthesis of The Conditional Operator, Index Op
 // Inference of Comparison Operators

/// 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.

//  Step-by-Step Genus Instructions (For this Course)
//        https://www.ece.lsu.edu/v/proc.html#synthesis
//
//  Genus HDL Modeling Guide -- Access from Within lsu.edu Only.
//        https://www.ece.lsu.edu/v/s/genus_hdlmod.pdf
//
//  Links to More Documentation and References
//        https://www.ece.lsu.edu/v/ref.html


////////////////////////////////////////////////////////////////////////////////
/// Inference of Expressions
//
 // :Def: Expression
 // An arrangement of operators and operands which returns a result, as
 // defined by some language, such as C++11 or SystemVerilog 2012.
 //
 // :Sample: x = a + b * ( c - d );
 //
 // We should be familiar with expressions in many computer languages.
 //

 // :Def: Operator Syntax
 // The rules for using the operator in code written in the language.

 // :Def: Operator Semantics
 // A description of how an operator transforms its operands into a result.
 //
 // :Sample: int a,b; ... a + b;
 // Semantics of +: Result is signed integer sum, overflow ignored.


 /// SystemVerilog Operator Treatment -- Simulation
 //
 //  SystemVerilog 2012 defines operators and expressions in Chapter 12.
 //  Syntax and semantics must (shall!) follow the standard.
 //  Semantics exactly described.


 /// SystemVerilog Operator Treatment -- Synthesis
 //
 //  Each synthesis program defines a synthesizable subset.
 //
 //  Cadence Genus
 //
 //    Synthesizable Subset Described In
 //      Genus HDL Modeling Guide
 //        See Chapter 4.


 // :Def: Synthesizable Operator
 // An operator that's synthesizable by a particular synthesis program.


 /// Arithmetic Operators v. Other Operators
 //
 //  For logical operators it is easy to infer hardware,
 //   for example  assign x = a && b; would be inferred as an AND gate.
 //
 //  Arithmetic operators inference is not so simple because of:
 //   Operand width (number of bits).
 //   Operand type (signed v. unsigned).
 //   Need to provide optimization flexibility.
 //
 //  Inference of arithmetic and non-arithmetic operators covered in
 //  this set.


////////////////////////////////////////////////////////////////////////////////
/// Inference of Arbitrary Expressions

 /// Steps
 //
 //  - Use precedence and association to determine order.
 //  - Draw diagram.


// :Example:
//
// Show inferred hardware for the expression in the module below.

module arb_exp
  ( output uwire [7:0] x,
    input uwire [8:0] a,
    input uwire [6:0] b, c,
    input uwire [2:0] e, f );

   assign x = a + b * c << ( e + f );

   /// Based on precedence and association:
   //
   // i1 = b*c;
   // i2 = a + i1;
   // i3 = e + f;
   // x = i2 << i3;
   //
   // Note: i1, i2, and i3 are not actually declared anywhere ..
   // .. they are used to make clear the order in which the operations
   //    are performed ..
   // .. and as labels in the diagram below.

endmodule

 // 



////////////////////////////////////////////////////////////////////////////////
/// Inference of Logical Operators
///


 /// Boolean Two-Operand Logical Operators
 //
 //  &&,  ||  (AND, OR)
 //  <->, ->  (XNOR (equivalence), implication)  Note: not implemented.
 //
 //  - Both arguments are Boolean types.
 //  - Result is a 1-bit unsigned integer.
 //  - Arguments are converted into Boolean types if necessary.
 //
 //  All these can be inferred in a straightforward manner.
 //  Synthesizes into the gate that you would expect.

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

   assign x = a && b;
   assign y = a || b;

endmodule

// 


 /// Conversion from Integer Types to Boolean Type
 //
 //  Integer Types
 //   Set l020 will cover types in detail.
 //   An example of an integer type is: uwire [7:0] a;
 //
 //  Conversion value a to Boolean:
 //    If a == 0, Boolean value is False.
 //    If a != 0, Boolean value is True.
 //    If a contains x's (undefined), Boolean value is x.
 //
 //  Synthesis of Integer-to-Boolean Conversion
 //
 //    For course assignments, assume that an n-bit integer
 //     is converted to a Boolean with an n-input OR gate.


// :Example:
//
// Convert 4-bit inputs a and b into Booleans, then perform AND operation.

module example_conversion
  (output uwire x,
   input uwire [3:0] a, b);

   assign x = a && b;
   //
   // Note that a and b are 4 bits each and that x is 1 bit.

endmodule

 // 


 /// Bitwise Logical Operators
 //
 //  &, |, ^,  (AND, OR, XOR)
 //
 //  - Both arguments are bit vectors.
 //  - Result is a bit vector at least as large as larger operand.
 //
 //  All these can be inferred in a straightforward manner.
 //  Synthesizes into a collection of gates, one gate for each bit.


module example_bitw_and
  (output uwire [3:0] x,
   input uwire [3:0] a, b);

   assign x = a & b;

endmodule

 // 

module example_bitw_and_or_xor
  (output uwire [3:0] x, y, z,
   input uwire [3:0] a, b);

   assign x = a & b;
   assign y = a | b;
   assign z = a ^ b;

endmodule



 /// Reduction Operators
 //
 //  Reduction operators convert multiple bits into one bit.
 //
 //  &, ~&, |, ~|, ^, ~^
 //
 //  - There is one argument, a bit vector.
 //  - In effect the operator is placed between adjacent bits ..
 //    .. for example, &x is equivalent to
 //    .. x[0] && x[1] && x[2] ..
 //    .. for x declared: logic x[0:2].
 //  - The result is one bit.
 //
 //  All these can be inferred in a straightforward manner.
 //  Synthesizes into a w-input gate, where w is the width of the operand.

module example_redlop
  (input uwire [3:0] a,
   output uwire x, y, z );

   assign x = & a;   // Equivalent to x = a[3] && a[2] && a[1] && a[0];
   assign y = | a;   // Reduction OR, same as conversion to Boolean.
   assign z = ^ a;   // Reduction XOR, true if odd number of bits 1.

endmodule



 /// Shift
 //
 //  <<,  >>   // Logical Shift Operators
 //  <<<, >>>  // Arithmetic Shift Operators
 //
 //  All these can be inferred in a straightforward manner.


 /// Concatenation
 //
 //  {}
 //
 //  Nothing to synthesize.




////////////////////////////////////////////////////////////////////////////////
/// Synthesis of The Conditional Operator
///

 /// The Conditional Operator (Review)
//
// Similar to the conditional operator in C, C++, C++11, ...
//
// :Sample:  x = s ? a : b;
// Equivalent to:  if ( s ) x = a; else x = b;

 /// The conditional operator (s?a:b) is synthesized as a multiplexor.
//
// :Sample: assign x = s ? a : b;
// Two-input mux, x is control, a and b are data inputs.


module conditional_review
  ( output int x, input logic s, input uwire [7:0] c, d );

   int a, b;

   initial begin

      a = 2;
      b = 3;

      // The two lines below do the same thing:
      //
      x = s ? a : b;
      if ( s ) x = a; else x = b;

      // The two lines below do the same thing:
      //
      x = c < d ? a : b + 1;
      if ( c < d ) x = a; else x = b+1;

      // The first line and the following lines do the same thing.
      //
      x = c < d ? a : c < 2 * d ? b : b + 2;
      if ( c < d )
        begin
           x = a;
        end
      else
        begin
           if ( c < 2 * d ) x = b; else x = b + 2;
        end
      //
      // Did you take the time to figure this out?

   end

endmodule


// :Example:
//
// Use of conditional operator to describe a two-input multiplexor.

module mux2
  ( output uwire [7:0] x,
    input uwire s,
    input uwire [7:0] a, b );

   assign x = s == 0 ? a : b;

endmodule

// 


// Note that a two-input multiplexor can be implemented using
// three gates per bit:

// 



// The following code containing chained conditional operators. This
// can be synthesized as three 2-input multiplxors or, because s is
// being tested for the sequence 0, 1, 3, a single multiple-input
// multiplexor.
//
// :Example:
//
// Use of conditional operator to describe a four-input multiplexor.


module mux4
  ( output uwire [7:0] x,
    input uwire [1:0] s,
    input uwire [7:0] a0, a1, a2, a3 );

    assign x =  s==0 ? a0 :
                s==1 ? a1 :
                s==2 ? a2 : a3;

endmodule


// Inferred as three 2-input multiplexors.
// 

// Inferred as one 4-input multiplexor.
// 



////////////////////////////////////////////////////////////////////////////////
/// Synthesis of The Index Operator
///

 /// Index Operator, []
//
//  :Sample:  a[5] // Access element 5 of a.
//
//  Used to access elements of a vector or array.
//  Some people are surprised to learn that "[]" is an operator. 

 /// The index operator [] is inferred as a mux.
//
//   Consider a[s] where
//     s is n-bit vector 
//     a is a 2^n-element array of vectors.

module mux16
  ( output uwire [7:0] x,
    input uwire [4:1] s,
    input uwire [15:0][7:0] a );

   assign      x = a[s];

endmodule

module muxn
  #( int w = 16,
     int n = 4,
     int lgn = $clog2(n) )
  ( output uwire [w:1] x,
    input uwire [lgn:1] s,
    input uwire [w:1] a[n] );

   assign      x = a[s];

endmodule



////////////////////////////////////////////////////////////////////////////////
/// Inference of Widths of Arithmetic Expressions
///

 /// Expression Width
 //
 //  The number of bits used for an intermediate value.
 //  Beware: Verilog can use fewer bits than you assume.

 /// Widths (Size)
 //
 //  :Def: Self-Determined Expression Context
 //  Size determined by expression itself, not the surrounding context.
 //
 //  :Example:
 //
 //  x = a << E;   // E is in a self-determined context (by def of << operator).
 //                // Therefore size of E does not depend on a or x.
 //
 //
 //  :Def: Context-Determined Expression Context
 //  Size determined by expression itself, and by how or where it is used.
 //
 //  :Example:
 //
 //  x = E + b;   // E is a context-determined operand (and so is b).
 //               // Size of E is maximum of sizes of x, E, and b.

 //  :Example:
 //
 //  x = E << b;  // E is a context-determined operand.
 //               // Size of E depends on size of x.


 /// Motivating Example
//
// :Example:
//
// The less than module below seems to be returning the wrong result.
// Why?

module less_than( output uwire lt, input uwire [6:0] a, b, amt );

   assign lt = a + b < amt;

endmodule

module less_than_tryout;
   logic [6:0] a, b, amt;
   uwire lt;

   less_than lt1(lt, a, b, amt);

   initial begin
      b = 35;
      amt = 100;

      for ( int av = 80; av < 120; av += 10 )
        begin
           a = av;
           #1;
           $write("Expression %d + %d < %d is: %s\n",
                  a, b, amt, lt ? "true" : "false");
        end
   end

   // Expression  80 +  35 < 100 is: false
   // Expression  90 +  35 < 100 is: false
   // Expression 100 +  35 < 100 is:  true
   // Expression 110 +  35 < 100 is:  true

endmodule




module example
  ( output uwire [4:0] x1, x2,
    input uwire [3:0] a, b,
    input uwire [6:0] c );

   assign x1 = ( a + b ) + c;
   //
   // Operands of + are context-determined,
   //  therefore width of adder inputs and outputs will be max(4,5,7) = 7;
   // x1 gets 5 LSB of result, the rest is discarded.

   assign x2 = a + b << c;
   //
   // c is self-determined, so its size stays at 7 (which is overkill).
   // Size of others is max(4,5) = 5.
   // Shifter's data input and outputs are 5 bits, shift amt is 7 bits.

endmodule


// :Example:
//
// Determine the bit widths of the intermediate values of expressions
// in the module below. See 2017 Midterm Exam Problem 4.
//
module wqf
  #( int w = 16 )
   ( output uwire signed [2*w-1:0] rad,
     output uwire [31:0] srad,
     input uwire [w-1:0] a, b, c );

   sqrt #(w) s1(srad,rad);

   always_comb begin

      rad = b*b - 4 * a * c;
      if ( rad < 0 ) rad = 0;

   end

endmodule

 // 


module sqrt #(int w=16)(output uwire [w:1] x, input uwire [w:1] a);
   // Warning: not usually synthesizable.
   assign x = a**0.5;
endmodule


////////////////////////////////////////////////////////////////////////////////
/// Inference of Comparison Operators
///

 /// Comparison
 //
 //  Ordinary comparison:  ==, !=,  >,   >=, <, <=
 //  Four-state compare:  ===, !==, ==?, !=?
 //
 //  - Result of all comparisons is one bit.
 //  - Several argument types possible: bit vectors, reals.
 //
 //  
 //  Synthesis programs will only work with ordinary comparisons of int types.
 //  Typically inferred into a library module.
 //  Magnitude comparison, such as >, <, can be implemented using subtraction.

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

   assign x = a > b;

endmodule


 /// Arithmetic Operators
 //
 //  +, -, /, *, **, %
 //
 //  - Multiple argument types, eg, signed bit vector, integer, real.
 //  - Result type and width depends on operands.
 //
 //  Synthesis programs (so far) limit operator and operand combinations ..
 //  .. for example the exponent of ** must be a constant.
 //  Typically inferred into a library module.
 //
 /// Be Careful
 //
 //  - Pay attention to rules on bit widths.
 //  - Pay attention to rules on signed/unsigned integers.
 //  - Don't impede optimization by limiting widths or by touching bits.

module example_arithmetic
  (output uwire [8:0] x,
   input uwire [7:0] a, b);

   assign x = a + b;
   //
   // Note: because of x's size, a+b performed at width of 9 bits.

endmodule

 // :Example: Example of how helping hurts.
 //
 // Goal is to compute (a+b)/2  ...
 // ... but using formula a + (b-a)/2.
 //
 // We would like efficient hardware with a + (b-a)/2.
 //
 // If arithmetic expression written cleanly ..
 // .. synthesis program will transform a+(b-a)/2 to (a+b)/2.
 //
 // If arithmetic expression mixed with logic ..
 // .. synthesis program may not be able to transform expression.

module example_avg_helping_hurt
  ( output uwire [7:0] avg,
    input uwire [7:0] a, b );

   uwire [7:0]   a_inv = ~a;
   uwire [7:0]   minus_a = a_inv + 1;

   uwire logic [7:0] diff = b + minus_a;
   assign avg = diff[7:1] + a;

endmodule

module example_avg_good
  ( output uwire signed [7:0] avg,
    input uwire signed [7:0] a, b );

   assign avg = a + ( b - a ) / 2;

endmodule

module example_avg_best
  ( output uwire signed [7:0] avg,
    input uwire signed [7:0] a, b );

   assign avg = ( 0 + a + b ) / 2;

endmodule




 /// Pay Attention To
 //
 //  Data type and number of bits of inputs.
 //  Data type and number of bits of outputs.
 //
 //  Changes in the number of bits.
 //  Interpretation of integer as signed or unsigned.





module bool_v_1bit
  ( output uwire y1, output uwire y2,
    input uwire [7:0] a, b );

   // Consider
   //
   assign y1 = a && b;
   //
   //  The && is defined for 1-bit operands.
   //  


   assign y2 = a & b;
   //
   // Note: y2's size should match a and b's.


endmodule