src/core/muldiv.bsv

   1 /*
   2 Copyright (c) 2013, IIT Madras
   3 All rights reserved.
   4
   5 Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
   6
   7 *  Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
   8 *  Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
   9 *  Neither the name of IIT Madras  nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
  10
  11 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  12 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  13 */
  14 package muldiv;
  15         /*====== Package import ==== */
  16         import FIFOF::*;
  17         import SpecialFIFOs::*;
  18         import UniqueWrappers::*;
  19         /*==== Project Import=== */
  20         import defined_types::*;
  21         `include "defined_parameters.bsv"
  22         /*====================== */
  23
  24         `define UnrollMul 8 // this means the number of bits being analysed simultaneously
  25         `define UnrollDiv 1
  26
  27         interface Ifc_muldiv;
  28                 method Action input_operands(Bit#(`Reg_width) in1, Bit#(`Reg_width) in2, Bit#(2) funct3, Bit#(1) word_flag, Bit#(1) is_mul);
  29                 method ActionValue#(Bit#(`Reg_width)) muldiv_result;
  30                 method Action flush;
  31         endinterface
  32
  33         function Bit#(73) func_mult(Bit#(9) op1, Bit#(65) op2);
  34                 Bit#(73) lv_result=  signExtend(op1)*signExtend(op2);
  35                 return lv_result;
  36         endfunction
  37
  38         function Bool is_op_zero(Bit#(56) op, Bit#(4) count);
  39                 Bool acc_7to0_is_zero  = op[7:0]==0;
  40                 Bool acc_15to8_is_zero = op[15:8]==0;
  41                 Bool acc_23to16_is_zero= op[23:16]==0;
  42                 Bool acc_31to24_is_zero= op[31:24]==0;
  43                 Bool acc_39to32_is_zero= op[39:32]==0;
  44                 Bool acc_47to40_is_zero= op[47:40]==0;
  45                 Bool acc_55to48_is_zero= op[55:48]==0;
  46
  47                 Bool acc_47to32_is_zero= acc_47to40_is_zero && acc_39to32_is_zero;
  48                 Bool acc_31to16_is_zero= acc_31to24_is_zero && acc_23to16_is_zero;
  49                 Bool acc_15to0_is_zero = acc_15to8_is_zero  && acc_7to0_is_zero;
  50                 Bool acc_31to0_is_zero = acc_31to16_is_zero && acc_15to0_is_zero;
  51
  52                 Bool earlyout= False;
  53                 if(count[2:1]=='b11)    //==6 or ==7
  54                         if(acc_55to48_is_zero && acc_47to32_is_zero && acc_31to0_is_zero)
  55                                 earlyout= True;
  56                 else if(count==5)
  57                         if(acc_47to32_is_zero && acc_31to0_is_zero)
  58                                 earlyout= True;
  59                 else if(count==4)
  60                         if(acc_39to32_is_zero && acc_31to0_is_zero)
  61                                 earlyout= True;
  62                 else if(count==3)
  63                         if(acc_31to0_is_zero)
  64                                 earlyout= True;
  65                 else if(count==2)
  66                         if(acc_23to16_is_zero && acc_15to0_is_zero)
  67                                 earlyout= True;
  68                 else begin
  69                         if(acc_15to0_is_zero)
  70                                 earlyout= True;
  71                 end
  72                 return earlyout;
  73         endfunction
  74
  75         (*synthesize*)
  76         (*descending_urgency = "input_operands, perform_n_restoring_steps"*)
  77         module mkmuldiv(Ifc_muldiv);
  78
  79                 Wrapper2#(Bit#(73), Bit#(73), Bit#(73))   wrapper_add_1     <- mkUniqueWrapper2( \+ );
  80                 Wrapper2#(Bit#(9), Bit#(65), Bit#(73))   wrapper_mul_1      <- mkUniqueWrapper2( func_mult );
  81                 Wrapper2#(Bit#(56), Bit#(4), Bool)   wrapper_is_op_zero <- mkUniqueWrapper2( is_op_zero );
  82
  83                 Reg#(Bit#(65)) multiplicand_divisor <-mkReg(0);                         // operand2
  84                 Reg#(Bit#(137)) accumulator <-mkReg(0);  // holds the accumulated results over the iterations
  85                 FIFOF#(Bit#(64)) ff_muldiv_result <-mkBypassFIFOF();                                    // to hold the final result
  86                 FIFOF#(Tuple5#(Bit#(`Reg_width), Bit#(`Reg_width),Bit#(2), Bit#(1), Bit#(1))) ff_input <-mkLFIFOF();                                    // to hold the final result
  87                 Reg#(Bit#(4)) rg_count[2]<-mkCReg(2,8);
  88                 Reg#(Bool) rg_signed<-mkReg(False);
  89                 Reg#(Bool) upper_bits<-mkReg(False);
  90                 Reg#(Bit#(1)) temp_multiplier_sign<-mkReg(0);
  91                 Reg#(Bit#(1)) rg_word_flag<-mkReg(0);
  92                 Reg#(Bit#(1)) rg_result_sign<-mkReg(0);
  93                 Reg#(Bool) rg_is_mul <-mkReg(False);
  94
  95                 //Only DIV
  96                 Reg#(Bit#(7)) rg_state_counter[2]<-mkCReg(2,0);                                                                         // to count the number of iterations
  97                 Reg#(Bit#(2)) rg_funct3 <-mkReg(0);
  98
  99                 rule unroll_multiplication(rg_is_mul && rg_count[1]!=8);
 100
 101                         //Bit#(137) x=partial_prod_generator(multiplier_sign,multiplicand,accumulator[1]);
 102                         Bit#(73) product<- wrapper_mul_1.func({temp_multiplier_sign,accumulator[7:0]}, multiplicand_divisor);
 103                         Bit#(73) new_accum<- wrapper_add_1.func(accumulator[136:64],product);
 104                         Bit#(137) x = {new_accum,accumulator[63:0]};
 105                         Int#(137) y = unpack(x);
 106                         y=y>>8;
 107                         x=pack(y);
 108                         Bool earlyout=False;
 109                         if(rg_count[1]==7)
 110                                 earlyout<- wrapper_is_op_zero.func(accumulator[63:8],rg_count[1]);
 111                         else
 112                                 earlyout<- wrapper_is_op_zero.func(accumulator[55:0],rg_count[1]);
 113                         `ifdef verbose $display($time,"\tAccumulator: %h Multiplicand: %h count: %d isHi: %b word: %b compl: %b sign: %b",x,multiplicand_divisor,rg_count[1],upper_bits, rg_word_flag, rg_signed,temp_multiplier_sign); `endif
 114                         `ifdef verbose $display($time,"\tx: %h y: %h",x,y); `endif
 115                         if(rg_count[1]==0 || earlyout)begin
 116                                 `ifdef verbose $display($time,"\tMUL/DIV: Ending Mul/Div operation"); `endif
 117                                 y = unpack(x);
 118                                 x=pack(y>>({2'b0,rg_count[1]}*8));
 119                                 `ifdef verbose $display($time,"\tx: %h y: %h",x,y); `endif
 120                                 if(rg_word_flag==1)
 121                                         x=signExtend(x[31:0]);
 122                                 if(upper_bits)
 123                                         ff_muldiv_result.enq(x[2*`Reg_width-1:`Reg_width]);
 124                                 else
 125                                         ff_muldiv_result.enq(x[`Reg_width-1:0]);
 126                                 rg_count[1]<=8;
 127                         end
 128                         else begin
 129                                 rg_count[1]<=rg_count[1]-1;
 130                                 accumulator<=x;
 131                         end
 132                         if(rg_count[1]==1 && rg_signed)
 133                                 temp_multiplier_sign<=rg_result_sign;
 134                 endrule
 135
 136                 rule perform_n_restoring_steps(!rg_is_mul && rg_count[1]!='d8);
 137                         Bit#(`Reg_width) divisor= multiplicand_divisor[`Reg_width-1:0];
 138                         Bit#(TAdd#(1,TMul#(2,`Reg_width))) remainder= truncate(accumulator);
 139                         Bit#(TAdd#(1,`Reg_width)) sub;
 140                         for (Integer i=0;i<`UnrollDiv;i=i+1)begin
 141                                 remainder=remainder<<1;
 142                                 Bit#(73) lv_add_op1= {8'd0,remainder[2*`Reg_width:`Reg_width]};
 143                                 Bit#(73) lv_add_op2= signExtend(~divisor+1);
 144                                 let lv_added_inter_res <- wrapper_add_1.func(lv_add_op1, lv_add_op2);
 145                                 sub= truncate(lv_added_inter_res);
 146                                 if(remainder[2*`Reg_width-1:`Reg_width]>=divisor)begin  // if subtraction is positive
 147                                         remainder[0]=1;
 148                                         remainder[2*`Reg_width:`Reg_width]=sub;                                 // restore
 149                                 end
 150                         end
 151                         //Bit#(TAdd#(1,`Reg_width)) lv_to_add= signExtend(~multiplicand_divisor[63:0]+1);
 152                         sub=accumulator[128:64]+signExtend(~multiplicand_divisor[63:0]+1);
 153                         if((rg_state_counter[1]==(64/`UnrollDiv)))begin // end of computation;
 154                                 rg_state_counter[1]<=0;
 155                                 rg_count[1]<='d8;
 156                                 if(rg_funct3[1]==1) // REM/REMU
 157                                         if(rg_word_flag==1)
 158                                                 remainder=signExtend(remainder[95:64]);
 159                                         else
 160                                                 remainder=signExtend(remainder[127:64]);
 161                                 else // DIV/DIVU
 162                                         if(rg_word_flag==1)
 163                                                 remainder=signExtend(remainder[31:0]);
 164                                         else
 165                                                 remainder=signExtend(remainder[63:0]);
 166
 167                                 if(rg_funct3[1]==0 && rg_signed) begin// DIVU
 168                                         remainder=~remainder+1;
 169                                 end
 170                                 else if(rg_funct3[1:0]=='b10 && remainder[`Reg_width-1]!=rg_result_sign) begin  // REMU/REM
 171                                         remainder=~remainder+1;
 172                                 end
 173                                 if(rg_word_flag==1)
 174                                         ff_muldiv_result.enq(signExtend(remainder[31:0]));
 175                                 else
 176                                         ff_muldiv_result.enq(remainder[`Reg_width-1:0]);
 177                         end
 178                         else begin
 179                                 accumulator[128:0]<=remainder;
 180                                 rg_state_counter[1]<=rg_state_counter[1]+1;
 181                         end
 182                 endrule
 183
 184                 rule first_stage(rg_count[1]==8);
 185                         ff_input.deq;
 186                         let {in1,in2,funct3,word_flag,is_mul}=ff_input.first;
 187                         `ifdef verbose $display($time,"\tMUL/DIV: in1: %h in2: %h funct3: %h word_flag: %h is_mul: %b",in1,in2,funct3,word_flag, is_mul); `endif
 188                         Bit#(1) in2_sign=funct3[1:0]==1?word_flag==1?in2[31]:in2[63]:0;
 189                         Bit#(1) in1_sign=(funct3[1]^funct3[0]) & ((word_flag==1)?in1[31]:in1[63]);
 190
 191                         Bit#(TAdd#(`Reg_width,1)) op1;
 192                         Bit#(TAdd#(`Reg_width,1)) op2;
 193                         if(is_mul==1) begin
 194                                 op1= word_flag==1? zeroExtend(in1[31:0]):{1'b0,in1};
 195                                 op2= word_flag==1? zeroExtend(in2[31:0]):{1'b0,in2};
 196                         end
 197                         else begin
 198                                 op1= word_flag==1? (funct3[0]==0?signExtend(in1[31:0]):zeroExtend(in1[31:0])): ({in1[63],in1[63:0]});
 199                 op2= word_flag==1?(funct3[0]==0?signExtend(in2[31:0]):zeroExtend(in2[31:0])):({in2[63],in2[63:0]});
 200
 201                                 op1=(funct3[0]==0 && op1[`Reg_width]==1)?~op1[`Reg_width-1:0]+1:op1[`Reg_width-1:0];
 202                                 op2=(funct3[0]==0 && op2[`Reg_width]==1)?~op2[`Reg_width-1:0]+1:op2[`Reg_width-1:0];
 203                         end
 204
 205                         rg_word_flag<=word_flag;
 206                         rg_is_mul<= unpack(is_mul);
 207                         Bool op1_31_to_0_is_zero= (op1[31:0]==0);
 208                         Bool op2_31_to_0_is_zero= (op2[31:0]==0);
 209                         Bool op1_is_zero= word_flag==1? op1_31_to_0_is_zero:(op1[63:0]==0 && op1_31_to_0_is_zero);
 210                         Bool op2_is_zero= word_flag==1? op2_31_to_0_is_zero:(op2[63:0]==0 && op2_31_to_0_is_zero);
 211
 212                         if(is_mul==0 && op2_is_zero) begin
 213                                 if(funct3[1]==1) begin  //REM/REMU operation
 214                                         if(word_flag==1)
 215                                                 ff_muldiv_result.enq(signExtend(in1[31:0]));
 216                                         else
 217                                                 ff_muldiv_result.enq(in1);
 218                                 end
 219                                 else begin                              //DIV/DIVU operation
 220                                         ff_muldiv_result.enq('1);
 221                                 end
 222                         end
 223                         else if(op1_is_zero) begin
 224                                 ff_muldiv_result.enq(0);
 225                                 rg_signed<=False;
 226                         end
 227                         else begin
 228                                 if(funct3==0) begin
 229                                         upper_bits<=False;              //used only for MUL
 230                                         if(is_mul==1)
 231                                                 rg_signed<=op1[`Reg_width-1]!=op2[`Reg_width-1];
 232                                         else
 233                                                 rg_signed<=op1[`Reg_width]!=op2[`Reg_width];
 234                                 end
 235                                 else begin
 236                                         upper_bits<=True;               //used only for MUL
 237                                         if(is_mul==1)
 238                                                 rg_signed<=unpack(in1_sign);
 239                                         else
 240                                                 rg_signed<= False;
 241                                 end
 242
 243                                 if(is_mul==1) begin
 244                                         //Bit#(73) product<- wrapper_mul_1.func({1'b0,op1[7:0]}, {in2_sign,op2[`Reg_width-1:0]});
 245                                         ////Bit#(73) new_accum<- wrapper_add_1.func(accumulator[1][136:64],product);
 246                                         //Bit#(137) x = {product,op1[`Reg_width-1:0]};
 247                                         //Int#(137) y = unpack(x);
 248                                         //y=y>>8;
 249                                         //x=pack(y);
 250                                         //`ifdef verbose $display("--- in1: %h in2: %h out: %h", {in2_sign,op2[7:0]}, op1, x); `endif
 251                                         //Bool earlyout<- wrapper_is_op_zero.func(op1[63:8],rg_count[1]);
 252                                         //if(earlyout) begin
 253                                         //      y=unpack(x);
 254                                         //      x=pack(y>>7*8);
 255                                         //      if(word_flag==1)
 256                                         //              x=signExtend(x[31:0]);
 257                                         //      if(funct3!=0)   //Upper bits
 258                                         //              ff_muldiv_result.enq(x[2*`Reg_width-1:`Reg_width]);
 259                                         //      else
 260                                         //              ff_muldiv_result.enq(x[`Reg_width-1:0]);
 261                                         //end
 262                                         //else begin
 263                                                 rg_result_sign<=op1[`Reg_width-1];
 264                                                 temp_multiplier_sign<=0;
 265                                                 multiplicand_divisor<={in2_sign,op2[63:0]};
 266                                                 accumulator<=zeroExtend(op1[63:0]);
 267                                                 rg_count[1]<=7;
 268                                         //end
 269                                         //`ifdef verbose $display($time,"\tAccumulator: %h Multiplicand: %h rg_count: %d",x,{in2_sign,op2[63:0]},rg_count[1]); `endif
 270                                 end
 271                                 else begin
 272                                         accumulator<= zeroExtend(op1[63:0]);
 273                                         rg_state_counter[1]<=1;
 274                                         rg_count[1]<= 4;
 275                                         multiplicand_divisor<= op2;
 276                                         rg_result_sign<= op1[`Reg_width];
 277                                         rg_funct3<= funct3;
 278                                 end
 279                         end
 280                 endrule
 281
 282                 method Action input_operands(Bit#(`Reg_width) in1, Bit#(`Reg_width) in2, Bit#(2) funct3, Bit#(1) word_flag, Bit#(1) is_mul) if(rg_count[1]==8);
 283                         ff_input.enq(tuple5(in1,in2,funct3,word_flag,is_mul));
 284                 endmethod
 285                 method ActionValue#(Bit#(`Reg_width)) muldiv_result;
 286                         ff_muldiv_result.deq;
 287                         return ff_muldiv_result.first();
 288                 endmethod
 289                 method Action flush;
 290                         rg_count[0]<=8;
 291                         rg_state_counter[0]<= 0;
 292                 endmethod
 293         endmodule
 294
 295         module mkTb(Empty);
 296                 Ifc_muldiv muldiv <-mkmuldiv();
 297                 UInt#(128) op1 = 'hfffffffffffffadb;//'h868c3b620d9a5d2c;//fffffffffffffbde;//'h8000000000000000; //'hfffffffffffffaef;//'h0000000000040000;//000000000fffff8a;//01d9a0aea837b4df;
 298                 UInt#(128) op2 = 'h000000000000004e;//'h868c3b620d9a5d2c;//fffffffffffffbde;//'h8000000000000000; //'hfffffffffffffaef;//'h000000003b48acdb;//fffffffffffff8d5;//04b8d2eb05855afa;
 299                 Bit#(2) funct=0;
 300                 UInt#(128) y = op1*op2;
 301                 Reg#(Bit#(32)) rg_clk <- mkReg(0);
 302                 rule give_ip;
 303                         `ifdef verbose $display($time," Giving Inputs : Op1: %d Op2: %d",op1,op2); `endif
 304                         muldiv.input_operands(pack(truncate(op1)),pack(truncate(op2)),funct,1,0);
 305                 endrule
 306
 307                 rule get_out;
 308                         let x <-muldiv.muldiv_result;
 309                         `ifdef verbose $display($time," Output: %h Expected: %h Match: %b",x,y,(zeroExtend(x)==pack(y))); `endif
 310                         $finish(0);
 311                 endrule
 312
 313                 rule rl_clk;
 314                         rg_clk<= rg_clk+1;
 315                         if(rg_clk=='d100)
 316                                 $finish(0);
 317                 endrule
 318         endmodule
 319 endpackage