mipssim.cc Source File

00001 // mipssim.cc -- simulate a MIPS R2/3000 processor
00002 //
00003 //   This code has been adapted from Ousterhout's MIPSSIM package.
00004 //   Byte ordering is little-endian, so we can be compatible with
00005 //   DEC RISC systems.
00006 //
00007 //   DO NOT CHANGE -- part of the machine emulation
00008 //
00009 // Copyright (c) 1992-1993 The Regents of the University of California.
00010 // All rights reserved.  See copyright.h for copyright notice and limitation 
00011 // of liability and disclaimer of warranty provisions.
00012 
00013 #include "copyright.h"
00014 
00015 #include "machine.h"
00016 #include "mipssim.h"
00017 #include "system.h"
00018 
00019 static void Mult(int a, int b, bool signedArith, int* hiPtr, int* loPtr);
00020 
00021 //----------------------------------------------------------------------
00022 // Machine::Run
00023 //      Simulate the execution of a user-level program on Nachos.
00024 //      Called by the kernel when the program starts up; never returns.
00025 //
00026 //      This routine is re-entrant, in that it can be called multiple
00027 //      times concurrently -- one for each thread executing user code.
00028 //----------------------------------------------------------------------
00029 
00030 void
00031 Machine::Run()
00032 {
00033     Instruction *instr = new Instruction;  // storage for decoded instruction
00034 
00035     if(DebugIsEnabled('m'))
00036         printf("Starting thread \"%s\" at time %d\n",
00037                currentThread->getName(), stats->totalTicks);
00038     interrupt->setStatus(UserMode);
00039     for (;;) {
00040         OneInstruction(instr);
00041         interrupt->OneTick();
00042         if (singleStep && (runUntilTime <= stats->totalTicks))
00043           Debugger();
00044     }
00045 }
00046 
00047 
00048 //----------------------------------------------------------------------
00049 // TypeToReg
00050 //      Retrieve the register # referred to in an instruction. 
00051 //----------------------------------------------------------------------
00052 
00053 static int 
00054 TypeToReg(RegType reg, Instruction *instr)
00055 {
00056     switch (reg) {
00057       case RS:
00058         return instr->rs;
00059       case RT:
00060         return instr->rt;
00061       case RD:
00062         return instr->rd;
00063       case EXTRA:
00064         return instr->extra;
00065       default:
00066         return -1;
00067     }
00068 }
00069 
00070 //----------------------------------------------------------------------
00071 // Machine::OneInstruction
00072 //      Execute one instruction from a user-level program
00073 //
00074 //      If there is any kind of exception or interrupt, we invoke the 
00075 //      exception handler, and when it returns, we return to Run(), which
00076 //      will re-invoke us in a loop.  This allows us to
00077 //      re-start the instruction execution from the beginning, in
00078 //      case any of our state has changed.  On a syscall,
00079 //      the OS software must increment the PC so execution begins
00080 //      at the instruction immediately after the syscall. 
00081 //
00082 //      This routine is re-entrant, in that it can be called multiple
00083 //      times concurrently -- one for each thread executing user code.
00084 //      We get re-entrancy by never caching any data -- we always re-start the
00085 //      simulation from scratch each time we are called (or after trapping
00086 //      back to the Nachos kernel on an exception or interrupt), and we always
00087 //      store all data back to the machine registers and memory before
00088 //      leaving.  This allows the Nachos kernel to control our behavior
00089 //      by controlling the contents of memory, the translation table,
00090 //      and the register set.
00091 //----------------------------------------------------------------------
00092 
00093 void
00094 Machine::OneInstruction(Instruction *instr)
00095 {
00096     int raw;
00097     int nextLoadReg = 0;        
00098     int nextLoadValue = 0;      // record delayed load operation, to apply
00099                                 // in the future
00100 
00101     // Fetch instruction 
00102     if (!machine->ReadMem(registers[PCReg], 4, &raw))
00103         return;                 // exception occurred
00104     instr->value = raw;
00105     instr->Decode();
00106 
00107     if (DebugIsEnabled('m')) {
00108        struct OpString *str = &opStrings[instr->opCode];
00109 
00110        ASSERT(instr->opCode <= MaxOpcode);
00111        printf("At PC = 0x%x: ", registers[PCReg]);
00112        printf(str->string, TypeToReg(str->args[0], instr), 
00113                 TypeToReg(str->args[1], instr), TypeToReg(str->args[2], instr));
00114        printf("\n");
00115        }
00116     
00117     // Compute next pc, but don't install in case there's an error or branch.
00118     int pcAfter = registers[NextPCReg] + 4;
00119     int sum, diff, tmp, value;
00120     unsigned int rs, rt, imm;
00121 
00122     // Execute the instruction (cf. Kane's book)
00123     switch (instr->opCode) {
00124         
00125       case OP_ADD:
00126         sum = registers[instr->rs] + registers[instr->rt];
00127         if (!((registers[instr->rs] ^ registers[instr->rt]) & SIGN_BIT) &&
00128             ((registers[instr->rs] ^ sum) & SIGN_BIT)) {
00129             RaiseException(OverflowException, 0);
00130             return;
00131         }
00132         registers[instr->rd] = sum;
00133         break;
00134         
00135       case OP_ADDI:
00136         sum = registers[instr->rs] + instr->extra;
00137         if (!((registers[instr->rs] ^ instr->extra) & SIGN_BIT) &&
00138             ((instr->extra ^ sum) & SIGN_BIT)) {
00139             RaiseException(OverflowException, 0);
00140             return;
00141         }
00142         registers[instr->rt] = sum;
00143         break;
00144         
00145       case OP_ADDIU:
00146         registers[instr->rt] = registers[instr->rs] + instr->extra;
00147         break;
00148         
00149       case OP_ADDU:
00150         registers[instr->rd] = registers[instr->rs] + registers[instr->rt];
00151         break;
00152         
00153       case OP_AND:
00154         registers[instr->rd] = registers[instr->rs] & registers[instr->rt];
00155         break;
00156         
00157       case OP_ANDI:
00158         registers[instr->rt] = registers[instr->rs] & (instr->extra & 0xffff);
00159         break;
00160         
00161       case OP_BEQ:
00162         if (registers[instr->rs] == registers[instr->rt])
00163             pcAfter = registers[NextPCReg] + IndexToAddr(instr->extra);
00164         break;
00165         
00166       case OP_BGEZAL:
00167         registers[R31] = registers[NextPCReg] + 4;
00168       case OP_BGEZ:
00169         if (!(registers[instr->rs] & SIGN_BIT))
00170             pcAfter = registers[NextPCReg] + IndexToAddr(instr->extra);
00171         break;
00172         
00173       case OP_BGTZ:
00174         if (registers[instr->rs] > 0)
00175             pcAfter = registers[NextPCReg] + IndexToAddr(instr->extra);
00176         break;
00177         
00178       case OP_BLEZ:
00179         if (registers[instr->rs] <= 0)
00180             pcAfter = registers[NextPCReg] + IndexToAddr(instr->extra);
00181         break;
00182         
00183       case OP_BLTZAL:
00184         registers[R31] = registers[NextPCReg] + 4;
00185       case OP_BLTZ:
00186         if (registers[instr->rs] & SIGN_BIT)
00187             pcAfter = registers[NextPCReg] + IndexToAddr(instr->extra);
00188         break;
00189         
00190       case OP_BNE:
00191         if (registers[instr->rs] != registers[instr->rt])
00192             pcAfter = registers[NextPCReg] + IndexToAddr(instr->extra);
00193         break;
00194         
00195       case OP_DIV:
00196         if (registers[instr->rt] == 0) {
00197             registers[LoReg] = 0;
00198             registers[HiReg] = 0;
00199         } else {
00200             registers[LoReg] =  registers[instr->rs] / registers[instr->rt];
00201             registers[HiReg] = registers[instr->rs] % registers[instr->rt];
00202         }
00203         break;
00204         
00205       case OP_DIVU:       
00206           rs = (unsigned int) registers[instr->rs];
00207           rt = (unsigned int) registers[instr->rt];
00208           if (rt == 0) {
00209               registers[LoReg] = 0;
00210               registers[HiReg] = 0;
00211           } else {
00212               tmp = rs / rt;
00213               registers[LoReg] = (int) tmp;
00214               tmp = rs % rt;
00215               registers[HiReg] = (int) tmp;
00216           }
00217           break;
00218         
00219       case OP_JAL:
00220         registers[R31] = registers[NextPCReg] + 4;
00221       case OP_J:
00222         pcAfter = (pcAfter & 0xf0000000) | IndexToAddr(instr->extra);
00223         break;
00224         
00225       case OP_JALR:
00226         registers[instr->rd] = registers[NextPCReg] + 4;
00227       case OP_JR:
00228         pcAfter = registers[instr->rs];
00229         break;
00230         
00231       case OP_LB:
00232       case OP_LBU:
00233         tmp = registers[instr->rs] + instr->extra;
00234         if (!machine->ReadMem(tmp, 1, &value))
00235             return;
00236 
00237         if ((value & 0x80) && (instr->opCode == OP_LB))
00238             value |= 0xffffff00;
00239         else
00240             value &= 0xff;
00241         nextLoadReg = instr->rt;
00242         nextLoadValue = value;
00243         break;
00244         
00245       case OP_LH:
00246       case OP_LHU:        
00247         tmp = registers[instr->rs] + instr->extra;
00248         if (tmp & 0x1) {
00249             RaiseException(AddressErrorException, tmp);
00250             return;
00251         }
00252         if (!machine->ReadMem(tmp, 2, &value))
00253             return;
00254 
00255         if ((value & 0x8000) && (instr->opCode == OP_LH))
00256             value |= 0xffff0000;
00257         else
00258             value &= 0xffff;
00259         nextLoadReg = instr->rt;
00260         nextLoadValue = value;
00261         break;
00262         
00263       case OP_LUI:
00264         DEBUG('m', "Executing: LUI r%d,%d\n", instr->rt, instr->extra);
00265         registers[instr->rt] = instr->extra << 16;
00266         break;
00267         
00268       case OP_LW:
00269         tmp = registers[instr->rs] + instr->extra;
00270         if (tmp & 0x3) {
00271             RaiseException(AddressErrorException, tmp);
00272             return;
00273         }
00274         if (!machine->ReadMem(tmp, 4, &value))
00275             return;
00276         nextLoadReg = instr->rt;
00277         nextLoadValue = value;
00278         break;
00279         
00280       case OP_LWL:        
00281         tmp = registers[instr->rs] + instr->extra;
00282 
00283         // ReadMem assumes all 4 byte requests are aligned on an even 
00284         // word boundary.  Also, the little endian/big endian swap code would
00285         // fail (I think) if the other cases are ever exercised.
00286         ASSERT((tmp & 0x3) == 0);  
00287 
00288         if (!machine->ReadMem(tmp, 4, &value))
00289             return;
00290         if (registers[LoadReg] == instr->rt)
00291             nextLoadValue = registers[LoadValueReg];
00292         else
00293             nextLoadValue = registers[instr->rt];
00294         switch (tmp & 0x3) {
00295           case 0:
00296             nextLoadValue = value;
00297             break;
00298           case 1:
00299             nextLoadValue = (nextLoadValue & 0xff) | (value << 8);
00300             break;
00301           case 2:
00302             nextLoadValue = (nextLoadValue & 0xffff) | (value << 16);
00303             break;
00304           case 3:
00305             nextLoadValue = (nextLoadValue & 0xffffff) | (value << 24);
00306             break;
00307         }
00308         nextLoadReg = instr->rt;
00309         break;
00310         
00311       case OP_LWR:
00312         tmp = registers[instr->rs] + instr->extra;
00313 
00314         // ReadMem assumes all 4 byte requests are aligned on an even 
00315         // word boundary.  Also, the little endian/big endian swap code would
00316         // fail (I think) if the other cases are ever exercised.
00317         ASSERT((tmp & 0x3) == 0);  
00318 
00319         if (!machine->ReadMem(tmp, 4, &value))
00320             return;
00321         if (registers[LoadReg] == instr->rt)
00322             nextLoadValue = registers[LoadValueReg];
00323         else
00324             nextLoadValue = registers[instr->rt];
00325         switch (tmp & 0x3) {
00326           case 0:
00327             nextLoadValue = (nextLoadValue & 0xffffff00) |
00328                 ((value >> 24) & 0xff);
00329             break;
00330           case 1:
00331             nextLoadValue = (nextLoadValue & 0xffff0000) |
00332                 ((value >> 16) & 0xffff);
00333             break;
00334           case 2:
00335             nextLoadValue = (nextLoadValue & 0xff000000)
00336                 | ((value >> 8) & 0xffffff);
00337             break;
00338           case 3:
00339             nextLoadValue = value;
00340             break;
00341         }
00342         nextLoadReg = instr->rt;
00343         break;
00344         
00345       case OP_MFHI:
00346         registers[instr->rd] = registers[HiReg];
00347         break;
00348         
00349       case OP_MFLO:
00350         registers[instr->rd] = registers[LoReg];
00351         break;
00352         
00353       case OP_MTHI:
00354         registers[HiReg] = registers[instr->rs];
00355         break;
00356         
00357       case OP_MTLO:
00358         registers[LoReg] = registers[instr->rs];
00359         break;
00360         
00361       case OP_MULT:
00362         Mult(registers[instr->rs], registers[instr->rt], TRUE,
00363              &registers[HiReg], &registers[LoReg]);
00364         break;
00365         
00366       case OP_MULTU:
00367         Mult(registers[instr->rs], registers[instr->rt], FALSE,
00368              &registers[HiReg], &registers[LoReg]);
00369         break;
00370         
00371       case OP_NOR:
00372         registers[instr->rd] = ~(registers[instr->rs] | registers[instr->rt]);
00373         break;
00374         
00375       case OP_OR:
00376         registers[instr->rd] = registers[instr->rs] | registers[instr->rs];
00377         break;
00378         
00379       case OP_ORI:
00380         registers[instr->rt] = registers[instr->rs] | (instr->extra & 0xffff);
00381         break;
00382         
00383       case OP_SB:
00384         if (!machine->WriteMem((unsigned) 
00385                 (registers[instr->rs] + instr->extra), 1, registers[instr->rt]))
00386             return;
00387         break;
00388         
00389       case OP_SH:
00390         if (!machine->WriteMem((unsigned) 
00391                 (registers[instr->rs] + instr->extra), 2, registers[instr->rt]))
00392             return;
00393         break;
00394         
00395       case OP_SLL:
00396         registers[instr->rd] = registers[instr->rt] << instr->extra;
00397         break;
00398         
00399       case OP_SLLV:
00400         registers[instr->rd] = registers[instr->rt] <<
00401             (registers[instr->rs] & 0x1f);
00402         break;
00403         
00404       case OP_SLT:
00405         if (registers[instr->rs] < registers[instr->rt])
00406             registers[instr->rd] = 1;
00407         else
00408             registers[instr->rd] = 0;
00409         break;
00410         
00411       case OP_SLTI:
00412         if (registers[instr->rs] < instr->extra)
00413             registers[instr->rt] = 1;
00414         else
00415             registers[instr->rt] = 0;
00416         break;
00417         
00418       case OP_SLTIU:      
00419         rs = registers[instr->rs];
00420         imm = instr->extra;
00421         if (rs < imm)
00422             registers[instr->rt] = 1;
00423         else
00424             registers[instr->rt] = 0;
00425         break;
00426         
00427       case OP_SLTU:       
00428         rs = registers[instr->rs];
00429         rt = registers[instr->rt];
00430         if (rs < rt)
00431             registers[instr->rd] = 1;
00432         else
00433             registers[instr->rd] = 0;
00434         break;
00435         
00436       case OP_SRA:
00437         registers[instr->rd] = registers[instr->rt] >> instr->extra;
00438         break;
00439         
00440       case OP_SRAV:
00441         registers[instr->rd] = registers[instr->rt] >>
00442             (registers[instr->rs] & 0x1f);
00443         break;
00444         
00445       case OP_SRL:
00446         tmp = registers[instr->rt];
00447         tmp >>= instr->extra;
00448         registers[instr->rd] = tmp;
00449         break;
00450         
00451       case OP_SRLV:
00452         tmp = registers[instr->rt];
00453         tmp >>= (registers[instr->rs] & 0x1f);
00454         registers[instr->rd] = tmp;
00455         break;
00456         
00457       case OP_SUB:        
00458         diff = registers[instr->rs] - registers[instr->rt];
00459         if (((registers[instr->rs] ^ registers[instr->rt]) & SIGN_BIT) &&
00460             ((registers[instr->rs] ^ diff) & SIGN_BIT)) {
00461             RaiseException(OverflowException, 0);
00462             return;
00463         }
00464         registers[instr->rd] = diff;
00465         break;
00466         
00467       case OP_SUBU:
00468         registers[instr->rd] = registers[instr->rs] - registers[instr->rt];
00469         break;
00470         
00471       case OP_SW:
00472         if (!machine->WriteMem((unsigned) 
00473                 (registers[instr->rs] + instr->extra), 4, registers[instr->rt]))
00474             return;
00475         break;
00476         
00477       case OP_SWL:        
00478         tmp = registers[instr->rs] + instr->extra;
00479 
00480         // The little endian/big endian swap code would
00481         // fail (I think) if the other cases are ever exercised.
00482         ASSERT((tmp & 0x3) == 0);  
00483 
00484         if (!machine->ReadMem((tmp & ~0x3), 4, &value))
00485             return;
00486         switch (tmp & 0x3) {
00487           case 0:
00488             value = registers[instr->rt];
00489             break;
00490           case 1:
00491             value = (value & 0xff000000) | ((registers[instr->rt] >> 8) &
00492                                             0xffffff);
00493             break;
00494           case 2:
00495             value = (value & 0xffff0000) | ((registers[instr->rt] >> 16) &
00496                                             0xffff);
00497             break;
00498           case 3:
00499             value = (value & 0xffffff00) | ((registers[instr->rt] >> 24) &
00500                                             0xff);
00501             break;
00502         }
00503         if (!machine->WriteMem((tmp & ~0x3), 4, value))
00504             return;
00505         break;
00506         
00507       case OP_SWR:        
00508         tmp = registers[instr->rs] + instr->extra;
00509 
00510         // The little endian/big endian swap code would
00511         // fail (I think) if the other cases are ever exercised.
00512         ASSERT((tmp & 0x3) == 0);  
00513 
00514         if (!machine->ReadMem((tmp & ~0x3), 4, &value))
00515             return;
00516         switch (tmp & 0x3) {
00517           case 0:
00518             value = (value & 0xffffff) | (registers[instr->rt] << 24);
00519             break;
00520           case 1:
00521             value = (value & 0xffff) | (registers[instr->rt] << 16);
00522             break;
00523           case 2:
00524             value = (value & 0xff) | (registers[instr->rt] << 8);
00525             break;
00526           case 3:
00527             value = registers[instr->rt];
00528             break;
00529         }
00530         if (!machine->WriteMem((tmp & ~0x3), 4, value))
00531             return;
00532         break;
00533         
00534       case OP_SYSCALL:
00535         RaiseException(SyscallException, 0);
00536         return; 
00537         
00538       case OP_XOR:
00539         registers[instr->rd] = registers[instr->rs] ^ registers[instr->rt];
00540         break;
00541         
00542       case OP_XORI:
00543         registers[instr->rt] = registers[instr->rs] ^ (instr->extra & 0xffff);
00544         break;
00545         
00546       case OP_RES:
00547       case OP_UNIMP:
00548         RaiseException(IllegalInstrException, 0);
00549         return;
00550         
00551       default:
00552         ASSERT(FALSE);
00553     }
00554     
00555     // Now we have successfully executed the instruction.
00556     
00557     // Do any delayed load operation
00558     DelayedLoad(nextLoadReg, nextLoadValue);
00559     
00560     // Advance program counters.
00561     registers[PrevPCReg] = registers[PCReg];    // for debugging, in case we
00562                                                 // are jumping into lala-land
00563     registers[PCReg] = registers[NextPCReg];
00564     registers[NextPCReg] = pcAfter;
00565 }
00566 
00567 //----------------------------------------------------------------------
00568 // Machine::DelayedLoad
00569 //      Simulate effects of a delayed load.
00570 //
00571 //      NOTE -- RaiseException/CheckInterrupts must also call DelayedLoad,
00572 //      since any delayed load must get applied before we trap to the kernel.
00573 //----------------------------------------------------------------------
00574 
00575 void
00576 Machine::DelayedLoad(int nextReg, int nextValue)
00577 {
00578     registers[registers[LoadReg]] = registers[LoadValueReg];
00579     registers[LoadReg] = nextReg;
00580     registers[LoadValueReg] = nextValue;
00581     registers[0] = 0;   // and always make sure R0 stays zero.
00582 }
00583 
00584 //----------------------------------------------------------------------
00585 // Instruction::Decode
00586 //      Decode a MIPS instruction 
00587 //----------------------------------------------------------------------
00588 
00589 void
00590 Instruction::Decode()
00591 {
00592     OpInfo *opPtr;
00593     
00594     rs = (value >> 21) & 0x1f;
00595     rt = (value >> 16) & 0x1f;
00596     rd = (value >> 11) & 0x1f;
00597     opPtr = &opTable[(value >> 26) & 0x3f];
00598     opCode = opPtr->opCode;
00599     if (opPtr->format == IFMT) {
00600         extra = value & 0xffff;
00601         if (extra & 0x8000) {
00602            extra |= 0xffff0000;
00603         }
00604     } else if (opPtr->format == RFMT) {
00605         extra = (value >> 6) & 0x1f;
00606     } else {
00607         extra = value & 0x3ffffff;
00608     }
00609     if (opCode == SPECIAL) {
00610         opCode = specialTable[value & 0x3f];
00611     } else if (opCode == BCOND) {
00612         int i = value & 0x1f0000;
00613 
00614         if (i == 0) {
00615             opCode = OP_BLTZ;
00616         } else if (i == 0x10000) {
00617             opCode = OP_BGEZ;
00618         } else if (i == 0x100000) {
00619             opCode = OP_BLTZAL;
00620         } else if (i == 0x110000) {
00621             opCode = OP_BGEZAL;
00622         } else {
00623             opCode = OP_UNIMP;
00624         }
00625     }
00626 }
00627 
00628 //----------------------------------------------------------------------
00629 // Mult
00630 //      Simulate R2000 multiplication.
00631 //      The words at *hiPtr and *loPtr are overwritten with the
00632 //      double-length result of the multiplication.
00633 //----------------------------------------------------------------------
00634 
00635 static void
00636 Mult(int a, int b, bool signedArith, int* hiPtr, int* loPtr)
00637 {
00638     if ((a == 0) || (b == 0)) {
00639         *hiPtr = *loPtr = 0;
00640         return;
00641     }
00642 
00643     // Compute the sign of the result, then make everything positive
00644     // so unsigned computation can be done in the main loop.
00645     bool negative = FALSE;
00646     if (signedArith) {
00647         if (a < 0) {
00648             negative = !negative;
00649             a = -a;
00650         }
00651         if (b < 0) {
00652             negative = !negative;
00653             b = -b;
00654         }
00655     }
00656 
00657     // Compute the result in unsigned arithmetic (check a's bits one at
00658     // a time, and add in a shifted value of b).
00659     unsigned int bLo = b;
00660     unsigned int bHi = 0;
00661     unsigned int lo = 0;
00662     unsigned int hi = 0;
00663     for (int i = 0; i < 32; i++) {
00664         if (a & 1) {
00665             lo += bLo;
00666             if (lo < bLo)  // Carry out of the low bits?
00667                 hi += 1;
00668             hi += bHi;
00669             if ((a & 0xfffffffe) == 0)
00670                 break;
00671         }
00672         bHi <<= 1;
00673         if (bLo & 0x80000000)
00674             bHi |= 1;
00675         
00676         bLo <<= 1;
00677         a >>= 1;
00678     }
00679 
00680     // If the result is supposed to be negative, compute the two's
00681     // complement of the double-word result.
00682     if (negative) {
00683         hi = ~hi;
00684         lo = ~lo;
00685         lo++;
00686         if (lo == 0)
00687             hi++;
00688     }
00689     
00690     *hiPtr = (int) hi;
00691     *loPtr = (int) lo;
00692 }