../src/lowrisc_ibex_ibex_core_0.1/rtl/ibex_multdiv_fast.sv Cov: 76%

   1: // Copyright lowRISC contributors.
   2: // Copyright 2018 ETH Zurich and University of Bologna, see also CREDITS.md.
   3: // Licensed under the Apache License, Version 2.0, see LICENSE for details.
   4: // SPDX-License-Identifier: Apache-2.0
   5: 
   6: `define OP_L 15:0
   7: `define OP_H 31:16
   8: 
   9: /**
  10:  * Fast Multiplier and Division
  11:  *
  12:  * 16x16 kernel multiplier and Long Division
  13:  */
  14: 
  15: `include "prim_assert.sv"
  16: 
  17: module ibex_multdiv_fast #(
  18:     parameter bit SingleCycleMultiply = 0
  19:   ) (
  20:     input  logic             clk_i,
  21:     input  logic             rst_ni,
  22:     input  logic             mult_en_i,  // dynamic enable signal, for FSM control
  23:     input  logic             div_en_i,   // dynamic enable signal, for FSM control
  24:     input  logic             mult_sel_i, // static decoder output, for data muxes
  25:     input  logic             div_sel_i,  // static decoder output, for data muxes
  26:     input  ibex_pkg::md_op_e operator_i,
  27:     input  logic  [1:0]      signed_mode_i,
  28:     input  logic [31:0]      op_a_i,
  29:     input  logic [31:0]      op_b_i,
  30:     input  logic [33:0]      alu_adder_ext_i,
  31:     input  logic [31:0]      alu_adder_i,
  32:     input  logic             equal_to_zero_i,
  33:     input  logic             data_ind_timing_i,
  34: 
  35:     output logic [32:0]      alu_operand_a_o,
  36:     output logic [32:0]      alu_operand_b_o,
  37: 
  38:     input  logic [33:0]      imd_val_q_i,
  39:     output logic [33:0]      imd_val_d_o,
  40:     output logic             imd_val_we_o,
  41: 
  42:     input  logic             multdiv_ready_id_i,
  43: 
  44:     output logic [31:0]      multdiv_result_o,
  45:     output logic             valid_o
  46: );
  47: 
  48:   import ibex_pkg::*;
  49: 
  50:   // Both multiplier variants
  51:   logic signed [34:0] mac_res_signed;
  52:   logic        [34:0] mac_res_ext;
  53:   logic        [33:0] accum;
  54:   logic        sign_a, sign_b;
  55:   logic        mult_valid;
  56:   logic        signed_mult;
  57: 
  58:   // Results that become intermediate value depending on whether mul or div is being calculated
  59:   logic [33:0] mac_res_d, op_remainder_d;
  60:   // Raw output of MAC calculation
  61:   logic [33:0] mac_res;
  62: 
  63:   // Divider signals
  64:   logic        div_sign_a, div_sign_b;
  65:   logic        is_greater_equal;
  66:   logic        div_change_sign, rem_change_sign;
  67:   logic [31:0] one_shift;
  68:   logic [31:0] op_denominator_q;
  69:   logic [31:0] op_numerator_q;
  70:   logic [31:0] op_quotient_q;
  71:   logic [31:0] op_denominator_d;
  72:   logic [31:0] op_numerator_d;
  73:   logic [31:0] op_quotient_d;
  74:   logic [31:0] next_remainder;
  75:   logic [32:0] next_quotient;
  76:   logic [32:0] res_adder_h;
  77:   logic        div_valid;
  78:   logic [ 4:0] div_counter_q, div_counter_d;
  79:   logic        multdiv_en;
  80:   logic        mult_hold;
  81:   logic        div_hold;
  82:   logic        div_by_zero_d, div_by_zero_q;
  83: 
  84:   logic        mult_en_internal;
  85:   logic        div_en_internal;
  86: 
  87:   typedef enum logic [2:0] {
  88:     MD_IDLE, MD_ABS_A, MD_ABS_B, MD_COMP, MD_LAST, MD_CHANGE_SIGN, MD_FINISH
  89:   } md_fsm_e;
  90:   md_fsm_e md_state_q, md_state_d;
  91: 
  92:   logic unused_mult_sel_i;
  93:   assign unused_mult_sel_i = mult_sel_i;
  94: 
  95:   assign mult_en_internal = mult_en_i & ~mult_hold;
  96:   assign div_en_internal  = div_en_i & ~div_hold;
  97: 
  98:   always_ff @(posedge clk_i or negedge rst_ni) begin
  99:     if (!rst_ni) begin
 100:       div_counter_q    <= '0;
 101:       md_state_q       <= MD_IDLE;
 102:       op_denominator_q <= '0;
 103:       op_numerator_q   <= '0;
 104:       op_quotient_q    <= '0;
 105:       div_by_zero_q    <= '0;
 106:     end else if (div_en_internal) begin
 107:       div_counter_q    <= div_counter_d;
 108:       op_denominator_q <= op_denominator_d;
 109:       op_numerator_q   <= op_numerator_d;
 110:       op_quotient_q    <= op_quotient_d;
 111:       md_state_q       <= md_state_d;
 112:       div_by_zero_q    <= div_by_zero_d;
 113:     end
 114:   end
 115: 
 116: 
 117:   `ASSERT_KNOWN(DivEnKnown, div_en_internal);
 118:   `ASSERT_KNOWN(MultEnKnown, mult_en_internal);
 119:   `ASSERT_KNOWN(MultDivEnKnown, multdiv_en);
 120: 
 121:   assign multdiv_en = mult_en_internal | div_en_internal;
 122: 
 123:   assign imd_val_d_o = div_sel_i ? op_remainder_d : mac_res_d;
 124:   assign imd_val_we_o = multdiv_en;
 125: 
 126:   assign signed_mult      = (signed_mode_i != 2'b00);
 127:   assign multdiv_result_o = div_sel_i ? imd_val_q_i[31:0] : mac_res_d[31:0];
 128: 
 129:   // The single cycle multiplier uses three 17 bit multipliers to compute MUL instructions in a
 130:   // single cycle and MULH instructions in two cycles.
 131:   if (SingleCycleMultiply) begin : gen_multiv_single_cycle
 132: 
 133:     typedef enum logic {
 134:       MULL, MULH
 135:     } mult_fsm_e;
 136:     mult_fsm_e mult_state_q, mult_state_d;
 137: 
 138:     logic signed [33:0] mult1_res, mult2_res, mult3_res;
 139:     logic [15:0]        mult1_op_a, mult1_op_b;
 140:     logic [15:0]        mult2_op_a, mult2_op_b;
 141:     logic [15:0]        mult3_op_a, mult3_op_b;
 142:     logic               mult1_sign_a, mult1_sign_b;
 143:     logic               mult2_sign_a, mult2_sign_b;
 144:     logic               mult3_sign_a, mult3_sign_b;
 145:     logic [33:0]        summand1, summand2, summand3;
 146: 
 147:     assign mult1_res = $signed({mult1_sign_a, mult1_op_a}) * $signed({mult1_sign_b, mult1_op_b});
 148:     assign mult2_res = $signed({mult2_sign_a, mult2_op_a}) * $signed({mult2_sign_b, mult2_op_b});
 149:     assign mult3_res = $signed({mult3_sign_a, mult3_op_a}) * $signed({mult3_sign_b, mult3_op_b});
 150: 
 151:     assign mac_res_signed = $signed(summand1) + $signed(summand2) + $signed(summand3);
 152: 
 153:     assign mac_res_ext    = $unsigned(mac_res_signed);
 154:     assign mac_res        = mac_res_ext[33:0];
 155: 
 156:     assign sign_a = signed_mode_i[0] & op_a_i[31];
 157:     assign sign_b = signed_mode_i[1] & op_b_i[31];
 158: 
 159:     // The first two multipliers are only used in state 1 (MULL). We can assign them statically.
 160:     // al*bl
 161:     assign mult1_sign_a = 1'b0;
 162:     assign mult1_sign_b = 1'b0;
 163:     assign mult1_op_a = op_a_i[`OP_L];
 164:     assign mult1_op_b = op_b_i[`OP_L];
 165: 
 166:     // al*bh
 167:     assign mult2_sign_a = 1'b0;
 168:     assign mult2_sign_b = sign_b;
 169:     assign mult2_op_a = op_a_i[`OP_L];
 170:     assign mult2_op_b = op_b_i[`OP_H];
 171: 
 172:     // used in MULH
 173:     assign accum[17:0] = imd_val_q_i[33:16];
 174:     assign accum[33:18] = {16{signed_mult & imd_val_q_i[33]}};
 175: 
 176:     always_comb begin
 177:       // Default values == MULL
 178: 
 179:       // ah*bl
 180:       mult3_sign_a = sign_a;
 181:       mult3_sign_b = 1'b0;
 182:       mult3_op_a = op_a_i[`OP_H];
 183:       mult3_op_b = op_b_i[`OP_L];
 184: 
 185:       summand1 = {18'h0, mult1_res[`OP_H]};
 186:       summand2 = mult2_res;
 187:       summand3 = mult3_res;
 188: 
 189:       // mac_res = A*B[47:16], mult1_res = A*B[15:0]
 190:       mac_res_d = {2'b0, mac_res[`OP_L], mult1_res[`OP_L]};
 191:       mult_valid = mult_en_i;
 192:       mult_state_d = MULL;
 193: 
 194:       mult_hold = 1'b0;
 195: 
 196:       unique case (mult_state_q)
 197: 
 198:         MULL: begin
 199:           if (operator_i != MD_OP_MULL) begin
 200:             mac_res_d = mac_res;
 201:             mult_valid = 1'b0;
 202:             mult_state_d = MULH;
 203:           end else begin
 204:             mult_hold = ~multdiv_ready_id_i;
 205:           end
 206:         end
 207: 
 208:         MULH: begin
 209:           // ah*bh
 210:           mult3_sign_a = sign_a;
 211:           mult3_sign_b = sign_b;
 212:           mult3_op_a = op_a_i[`OP_H];
 213:           mult3_op_b = op_b_i[`OP_H];
 214:           mac_res_d = mac_res;
 215: 
 216:           summand1 = '0;
 217:           summand2 = accum;
 218:           summand3 = mult3_res;
 219: 
 220:           mult_state_d = MULL;
 221:           mult_valid = 1'b1;
 222: 
 223:           mult_hold = ~multdiv_ready_id_i;
 224:         end
 225: 
 226:         default: begin
 227:           mult_state_d = MULL;
 228:         end
 229: 
 230:       endcase // mult_state_q
 231:     end
 232: 
 233:     always_ff @(posedge clk_i or negedge rst_ni) begin
 234:       if (!rst_ni) begin
 235:         mult_state_q <= MULL;
 236:       end else begin
 237:         if (mult_en_internal) begin
 238:           mult_state_q <= mult_state_d;
 239:         end
 240:       end
 241:     end
 242: 
 243:     // States must be knwon/valid.
 244:     `ASSERT_KNOWN(IbexMultStateKnown, mult_state_q)
 245: 
 246:   // The fast multiplier uses one 17 bit multiplier to compute MUL instructions in 3 cycles
 247:   // and MULH instructions in 4 cycles.
 248:   end else begin : gen_multdiv_fast
 249:     logic [15:0] mult_op_a;
 250:     logic [15:0] mult_op_b;
 251: 
 252:     typedef enum logic [1:0] {
 253:       ALBL, ALBH, AHBL, AHBH
 254:     } mult_fsm_e;
 255:     mult_fsm_e mult_state_q, mult_state_d;
 256: 
 257:     // The 2 MSBs of mac_res_ext (mac_res_ext[34:33]) are always equal since:
 258:     // 1. The 2 MSBs of the multiplicants are always equal, and
 259:     // 2. The 16 MSBs of the addend (accum[33:18]) are always equal.
 260:     // Thus, it is safe to ignore mac_res_ext[34].
 261:     assign mac_res_signed =
 262:         $signed({sign_a, mult_op_a}) * $signed({sign_b, mult_op_b}) + $signed(accum);
 263:     assign mac_res_ext    = $unsigned(mac_res_signed);
 264:     assign mac_res        = mac_res_ext[33:0];
 265: 
 266:     always_comb begin
 267:       mult_op_a    = op_a_i[`OP_L];
 268:       mult_op_b    = op_b_i[`OP_L];
 269:       sign_a       = 1'b0;
 270:       sign_b       = 1'b0;
 271:       accum        = imd_val_q_i;
 272:       mac_res_d    = mac_res;
 273:       mult_state_d = mult_state_q;
 274:       mult_valid   = 1'b0;
 275:       mult_hold    = 1'b0;
 276: 
 277:       unique case (mult_state_q)
 278: 
 279:         ALBL: begin
 280:           // al*bl
 281:           mult_op_a = op_a_i[`OP_L];
 282:           mult_op_b = op_b_i[`OP_L];
 283:           sign_a    = 1'b0;
 284:           sign_b    = 1'b0;
 285:           accum     = '0;
 286:           mac_res_d = mac_res;
 287:           mult_state_d = ALBH;
 288:         end
 289: 
 290:         ALBH: begin
 291:           // al*bh<<16
 292:           mult_op_a = op_a_i[`OP_L];
 293:           mult_op_b = op_b_i[`OP_H];
 294:           sign_a    = 1'b0;
 295:           sign_b    = signed_mode_i[1] & op_b_i[31];
 296:           // result of AL*BL (in imd_val_q_i) always unsigned with no carry, so carries_q always 00
 297:           accum     = {18'b0, imd_val_q_i[31:16]};
 298:           if (operator_i == MD_OP_MULL) begin
 299:             mac_res_d = {2'b0, mac_res[`OP_L], imd_val_q_i[`OP_L]};
 300:           end else begin
 301:             // MD_OP_MULH
 302:             mac_res_d = mac_res;
 303:           end
 304:           mult_state_d = AHBL;
 305:         end
 306: 
 307:         AHBL: begin
 308:           // ah*bl<<16
 309:           mult_op_a = op_a_i[`OP_H];
 310:           mult_op_b = op_b_i[`OP_L];
 311:           sign_a    = signed_mode_i[0] & op_a_i[31];
 312:           sign_b    = 1'b0;
 313:           if (operator_i == MD_OP_MULL) begin
 314:             accum        = {18'b0, imd_val_q_i[31:16]};
 315:             mac_res_d    = {2'b0, mac_res[15:0], imd_val_q_i[15:0]};
 316:             mult_valid   = 1'b1;
 317: 
 318:             // Note no state transition will occur if mult_hold is set
 319:             mult_state_d = ALBL;
 320:             mult_hold    = ~multdiv_ready_id_i;
 321:           end else begin
 322:             accum        = imd_val_q_i;
 323:             mac_res_d    = mac_res;
 324:             mult_state_d = AHBH;
 325:           end
 326:         end
 327: 
 328:         AHBH: begin
 329:           // only MD_OP_MULH here
 330:           // ah*bh
 331:           mult_op_a = op_a_i[`OP_H];
 332:           mult_op_b = op_b_i[`OP_H];
 333:           sign_a    = signed_mode_i[0] & op_a_i[31];
 334:           sign_b    = signed_mode_i[1] & op_b_i[31];
 335:           accum[17: 0]  = imd_val_q_i[33:16];
 336:           accum[33:18]  = {16{signed_mult & imd_val_q_i[33]}};
 337:           // result of AH*BL is not signed only if signed_mode_i == 2'b00
 338:           mac_res_d    = mac_res;
 339:           mult_valid   = 1'b1;
 340: 
 341:           // Note no state transition will occur if mult_hold is set
 342:           mult_state_d = ALBL;
 343:           mult_hold    = ~multdiv_ready_id_i;
 344:         end
 345:         default: begin
 346:           mult_state_d = ALBL;
 347:         end
 348:       endcase // mult_state_q
 349:     end
 350: 
 351:     always_ff @(posedge clk_i or negedge rst_ni) begin
 352:       if (!rst_ni) begin
 353:         mult_state_q <= ALBL;
 354:       end else begin
 355:         if (mult_en_internal) begin
 356:           mult_state_q <= mult_state_d;
 357:         end
 358:       end
 359:     end
 360: 
 361:     // States must be knwon/valid.
 362:     `ASSERT_KNOWN(IbexMultStateKnown, mult_state_q)
 363: 
 364:   end // gen_multdiv_fast
 365: 
 366:   // Divider
 367:   assign res_adder_h    = alu_adder_ext_i[33:1];
 368: 
 369:   assign next_remainder = is_greater_equal ? res_adder_h[31:0] : imd_val_q_i[31:0];
 370:   assign next_quotient  = is_greater_equal ? {1'b0, op_quotient_q} | {1'b0, one_shift} :
 371:                                              {1'b0, op_quotient_q};
 372: 
 373:   assign one_shift      = {31'b0, 1'b1} << div_counter_q;
 374: 
 375:   // The adder in the ALU computes alu_operand_a_o + alu_operand_b_o which means
 376:   // Remainder - Divisor. If Remainder - Divisor >= 0, is_greater_equal is equal to 1,
 377:   // the next Remainder is Remainder - Divisor contained in res_adder_h and the
 378:   always_comb begin
 379:     if ((imd_val_q_i[31] ^ op_denominator_q[31]) == 1'b0) begin
 380:       is_greater_equal = (res_adder_h[31] == 1'b0);
 381:     end else begin
 382:       is_greater_equal = imd_val_q_i[31];
 383:     end
 384:   end
 385: 
 386:   assign div_sign_a      = op_a_i[31] & signed_mode_i[0];
 387:   assign div_sign_b      = op_b_i[31] & signed_mode_i[1];
 388:   assign div_change_sign = (div_sign_a ^ div_sign_b) & ~div_by_zero_q;
 389:   assign rem_change_sign = div_sign_a;
 390: 
 391: 
 392:   always_comb begin
 393:     div_counter_d    = div_counter_q - 5'h1;
 394:     op_remainder_d   = imd_val_q_i;
 395:     op_quotient_d    = op_quotient_q;
 396:     md_state_d       = md_state_q;
 397:     op_numerator_d   = op_numerator_q;
 398:     op_denominator_d = op_denominator_q;
 399:     alu_operand_a_o  = {32'h0  , 1'b1};
 400:     alu_operand_b_o  = {~op_b_i, 1'b1};
 401:     div_valid        = 1'b0;
 402:     div_hold         = 1'b0;
 403:     div_by_zero_d    = div_by_zero_q;
 404: 
 405:     unique case(md_state_q)
 406:       MD_IDLE: begin
 407:         if (operator_i == MD_OP_DIV) begin
 408:           // Check if the Denominator is 0
 409:           // quotient for division by 0 is specified to be -1
 410:           // Note with data-independent time option, the full divide operation will proceed as
 411:           // normal and will naturally return -1
 412:           op_remainder_d = '1;
 413:           md_state_d     = (!data_ind_timing_i && equal_to_zero_i) ? MD_FINISH : MD_ABS_A;
 414:           // Record that this is a div by zero to stop the sign change at the end of the
 415:           // division (in data_ind_timing mode).
 416:           div_by_zero_d  = equal_to_zero_i;
 417:         end else begin
 418:           // Check if the Denominator is 0
 419:           // remainder for division by 0 is specified to be the numerator (operand a)
 420:           // Note with data-independent time option, the full divide operation will proceed as
 421:           // normal and will naturally return operand a
 422:           op_remainder_d = {2'b0, op_a_i};
 423:           md_state_d     = (!data_ind_timing_i && equal_to_zero_i) ? MD_FINISH : MD_ABS_A;
 424:         end
 425:         // 0 - B = 0 iff B == 0
 426:         alu_operand_a_o  = {32'h0  , 1'b1};
 427:         alu_operand_b_o  = {~op_b_i, 1'b1};
 428:         div_counter_d    = 5'd31;
 429:       end
 430: 
 431:       MD_ABS_A: begin
 432:         // quotient
 433:         op_quotient_d   = '0;
 434:         // A abs value
 435:         op_numerator_d  = div_sign_a ? alu_adder_i : op_a_i;
 436:         md_state_d      = MD_ABS_B;
 437:         div_counter_d   = 5'd31;
 438:         // ABS(A) = 0 - A
 439:         alu_operand_a_o = {32'h0  , 1'b1};
 440:         alu_operand_b_o = {~op_a_i, 1'b1};
 441:       end
 442: 
 443:       MD_ABS_B: begin
 444:         // remainder
 445:         op_remainder_d   = { 33'h0, op_numerator_q[31]};
 446:         // B abs value
 447:         op_denominator_d = div_sign_b ? alu_adder_i : op_b_i;
 448:         md_state_d       = MD_COMP;
 449:         div_counter_d    = 5'd31;
 450:         // ABS(B) = 0 - B
 451:         alu_operand_a_o  = {32'h0  , 1'b1};
 452:         alu_operand_b_o  = {~op_b_i, 1'b1};
 453:       end
 454: 
 455:       MD_COMP: begin
 456:         op_remainder_d  = {1'b0, next_remainder[31:0], op_numerator_q[div_counter_d]};
 457:         op_quotient_d   = next_quotient[31:0];
 458:         md_state_d      = (div_counter_q == 5'd1) ? MD_LAST : MD_COMP;
 459:         // Division
 460:         alu_operand_a_o = {imd_val_q_i[31:0], 1'b1}; // it contains the remainder
 461:         alu_operand_b_o = {~op_denominator_q[31:0], 1'b1};  // -denominator two's compliment
 462:       end
 463: 
 464:       MD_LAST: begin
 465:         if (operator_i == MD_OP_DIV) begin
 466:           // this time we save the quotient in op_remainder_d (i.e. imd_val_q_i) since
 467:           // we do not need anymore the remainder
 468:           op_remainder_d = {1'b0, next_quotient};
 469:         end else begin
 470:           // this time we do not save the quotient anymore since we need only the remainder
 471:           op_remainder_d = {2'b0, next_remainder[31:0]};
 472:         end
 473:         // Division
 474:         alu_operand_a_o  = {imd_val_q_i[31:0], 1'b1}; // it contains the remainder
 475:         alu_operand_b_o  = {~op_denominator_q[31:0], 1'b1};  // -denominator two's compliment
 476: 
 477:         md_state_d = MD_CHANGE_SIGN;
 478:       end
 479: 
 480:       MD_CHANGE_SIGN: begin
 481:         md_state_d  = MD_FINISH;
 482:         if (operator_i == MD_OP_DIV) begin
 483:           op_remainder_d = (div_change_sign) ? {2'h0, alu_adder_i} : imd_val_q_i;
 484:         end else begin
 485:           op_remainder_d = (rem_change_sign) ? {2'h0, alu_adder_i} : imd_val_q_i;
 486:         end
 487:         // ABS(Quotient) = 0 - Quotient (or Remainder)
 488:         alu_operand_a_o  = {32'h0  , 1'b1};
 489:         alu_operand_b_o  = {~imd_val_q_i[31:0], 1'b1};
 490:       end
 491: 
 492:       MD_FINISH: begin
 493:         // Hold result until ID stage is ready to accept it
 494:         // Note no state transition will occur if div_hold is set
 495:         md_state_d = MD_IDLE;
 496:         div_hold   = ~multdiv_ready_id_i;
 497:         div_valid   = 1'b1;
 498:       end
 499: 
 500:       default: begin
 501:         md_state_d = MD_IDLE;
 502:       end
 503:     endcase // md_state_q
 504:   end
 505: 
 506:   assign valid_o = mult_valid | div_valid;
 507: 
 508:   // States must be knwon/valid.
 509:   `ASSERT(IbexMultDivStateValid, md_state_q inside {
 510:       MD_IDLE, MD_ABS_A, MD_ABS_B, MD_COMP, MD_LAST, MD_CHANGE_SIGN, MD_FINISH})
 511: 
 512: endmodule // ibex_mult
 513: