![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mips.tex CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / sml / doc / mips|
Return to mips.tex CVS log | Up to [Research Unix] / researchv10no / cmd / sml / doc / mips |
1.1 ! root 1: \input nwmac ! 2: \filename{mipsglue.nw} ! 3: \begindocs{0} ! 4: \enddocs ! 5: \begindocs{1} ! 6: For the Mips, all comments are no-ops, so to get diagnostics in ! 7: assembly mode we have to slip in and define a new comment function. ! 8: Our life is further complicated by the fact that the stream on which ! 9: comments are to be written is bound late, so we have to save up comments ! 10: and then write them when asked to \code{}generate\edoc{}. ! 11: \enddocs ! 12: \begincode{2} ! 13: \moddef{*}\endmoddef ! 14: structure MipsAC : ASSEMBLER = struct ! 15: val diag_out = ref std_out ! 16: structure MCN = struct ! 17: open MipsCoder ! 18: structure M = struct ! 19: open M ! 20: fun comment s = output (!diag_out) s ! 21: end ! 22: end ! 23: ! 24: structure CM = MipsCM(MCN) ! 25: ! 26: structure Gen = CPScomp(CM) ! 27: fun generate (lexp, stream) = ( ! 28: diag_out := stream; ! 29: Gen.compile lexp; ! 30: MipsCoder.codestats stream; ! 31: Emitters.address := 0; ! 32: MipsCoder.codegen (Emitters.MipsAsm stream); ! 33: ()) ! 34: end ! 35: ! 36: \endcode ! 37: \begincode{3} ! 38: \moddef{*}\endmoddef ! 39: structure MipsCodeStats : ASSEMBLER = struct ! 40: val diag_out = ref std_out ! 41: structure MCN = MipsCoder ! 42: ! 43: structure CM = MipsCM(MCN) ! 44: ! 45: structure Gen = CPScomp(CM) ! 46: fun generate (lexp, stream) = ( ! 47: Gen.compile lexp; ! 48: MipsCoder.codestats stream; ! 49: ()) ! 50: end ! 51: ! 52: \endcode ! 53: \begindocs{4} ! 54: Mips machines come in two byte-orders, so we need two of ! 55: every machinelike thing. ! 56: \enddocs ! 57: \begincode{5} ! 58: \moddef{*}\endmoddef ! 59: structure MipsMCBig : CODEGENERATOR = struct ! 60: structure CM = MipsCM(MipsCoder) ! 61: structure Gen = CPScomp(CM) ! 62: ! 63: fun generate lexp = ( ! 64: Gen.compile lexp; ! 65: MipsCoder.codegen (Emitters.BigEndian); ! 66: Emitters.emitted_string () ! 67: ) ! 68: end ! 69: ! 70: structure MipsMCLittle : CODEGENERATOR = struct ! 71: structure CM = MipsCM(MipsCoder) ! 72: structure Gen = CPScomp(CM) ! 73: fun diag (s : string) f x = ! 74: f x handle e => ! 75: (print "?exception "; print (System.exn_name e); ! 76: print " in mipsglue."; print s; print "\\n"; ! 77: raise e) ! 78: ! 79: fun generate lexp = ( ! 80: diag "Gen.compile" Gen.compile lexp; ! 81: diag "MipsCoder.codegen" MipsCoder.codegen (Emitters.LittleEndian); ! 82: diag "Emitters.emitted_string" Emitters.emitted_string () ! 83: ) ! 84: end ! 85: ! 86: ! 87: structure CompMipsLittle = Batch(structure M=MipsMCLittle and A=MipsAC) ! 88: structure IntMipsLittle = IntShare(MipsMCLittle) ! 89: ! 90: structure CompMipsBig = Batch(structure M=MipsMCBig and A=MipsAC) ! 91: structure IntMipsBig = IntShare(MipsMCBig) ! 92: ! 93: structure CompMipsStats = Batch(structure M=MipsMCLittle and A=MipsCodeStats) ! 94: \endcode ! 95: \filename{emitters.nw} ! 96: \begindocs{0} ! 97: \section{Emitters} ! 98: We have an odd problem---we need to be able to emit either a 32-bit ! 99: integer or a string. ! 100: The order in which the bytes of the integer are emitted depends on ! 101: whether the target machine is BigEndian or LittleEndian, but the ! 102: bytes of the string should be emitted in the same order on both machines. ! 103: This means that the two emission functions depend on each other, but ! 104: in a machine-dependent way, so we bundle them up. ! 105: We also have to be able to emit two words for floating point constants. ! 106: The way to do this can be derived from \code{}emit_word\edoc{}, and this ! 107: code seems to be the sensible place to do that. ! 108: So we define a type \code{}emitter_triple\edoc{} ! 109: and pass them around that way. ! 110: ! 111: \enddocs ! 112: \begindocs{1} ! 113: Eventually we want to take all the words and strings that have been ! 114: emitted and bundle them up into a single string using \code{}implode\edoc{}. ! 115: We'll take the following tack with that: ! 116: each emitter will squirrel some info away in a reference variable. ! 117: A function \code{}emitted_string: unit -> string\edoc{} will take the ! 118: squirreled information and return a string that represents ! 119: everything emitted so far. ! 120: As a side effect, it will reset the emitter system to its initial ! 121: state, where ``everything emitted so far'' is the empty string. ! 122: ! 123: The actual implementation will be a list of strings which is reversed ! 124: and imploded. ! 125: \enddocs ! 126: \begincode{2} ! 127: \moddef{signature}\endmoddef ! 128: signature EMITTERS = sig ! 129: type emitter_triple ! 130: val LittleEndian : emitter_triple ! 131: val BigEndian : emitter_triple ! 132: val emitted_string : unit -> string ! 133: val MipsAsm : outstream -> emitter_triple ! 134: val address : int ref ! 135: end ! 136: ! 137: \endcode ! 138: \begindocs{3} ! 139: First something that's capable of emitting real code, then ! 140: something that can print assembly code. ! 141: We emit the assembly code to output right away, without any fooling. ! 142: \enddocs ! 143: \begincode{4} ! 144: \moddef{*}\endmoddef ! 145: structure Emitters : EMITTERS = struct ! 146: type emitter_triple = (int * int -> unit) * (int -> string -> unit) ! 147: * (string -> unit) ! 148: local ! 149: \LA{}memory and basic services\RA{} ! 150: in ! 151: \LA{}string emitter\RA{} ! 152: \LA{}little-endian emitter\RA{} ! 153: \LA{}big-endian emitter\RA{} ! 154: fun emitted_string () = ! 155: let val s = implode (rev (!so_far)) ! 156: in so_far := nil; s ! 157: end ! 158: end ! 159: structure BigReal = MipsReal(struct val emit_word = emit_pair_big end) ! 160: structure LittleReal =MipsReal(struct val emit_word = emit_pair_little end) ! 161: val LittleEndian = (emit_pair_little,emit_string,LittleReal.realconst) ! 162: val BigEndian = (emit_pair_big,emit_string,BigReal.realconst) ! 163: \LA{}assembly-code emitters\RA{} ! 164: end ! 165: ! 166: ! 167: \endcode ! 168: \begindocs{5} ! 169: Here is a variable to remember what's been emitted so far ! 170: \enddocs ! 171: \begincode{6} ! 172: \moddef{memory and basic services}\endmoddef ! 173: val so_far = ref nil : string list ref ! 174: fun squirrel s = so_far := s :: !so_far ! 175: fun emit_byte n = squirrel (chr n) ! 176: \endcode ! 177: \begincode{7} ! 178: \moddef{string emitter}\endmoddef ! 179: fun emit_string n s = squirrel (substring(s,0,n)) ! 180: handle e => ! 181: (print "?exception "; print (System.exn_name e); ! 182: print (" in emitters.emit_string "^ ! 183: (Integer.makestring n) ^ " \\""^s^"\\"\\n"); ! 184: raise e) ! 185: ! 186: \endcode ! 187: \begindocs{8} ! 188: Little-endian means the little (least significant) end first, ! 189: like the VAX. ! 190: We parameterize the real emitters by a function that emits a byte. ! 191: \enddocs ! 192: \begincode{9} ! 193: \moddef{little-endian emitter}\endmoddef ! 194: fun emit_pair_little(hi,lo) = ! 195: let open Bits ! 196: fun emit_word(n) = ! 197: (emit_byte(andb(n,255));emit_byte(andb(rshift(n,8),255))) ! 198: in (emit_word(lo);emit_word(hi)) ! 199: end ! 200: ! 201: \endcode ! 202: \begincode{10} ! 203: \moddef{big-endian emitter}\endmoddef ! 204: fun emit_pair_big(hi,lo) = ! 205: let open Bits ! 206: fun emit_word(n) = ! 207: (emit_byte(andb(rshift(n,8),255));emit_byte(andb(n,255))) ! 208: in (emit_word(hi);emit_word(lo)) ! 209: end ! 210: ! 211: ! 212: \endcode ! 213: \begindocs{11} ! 214: Now the assembly code. ! 215: to make it easier to debug, we print out addresses in the same format ! 216: as {\tt dbx}: we use the byte address and we print it in hex. ! 217: ! 218: We have to bend over backwards to handle real numbers ! 219: ! 220: \enddocs ! 221: \begincode{12} ! 222: \moddef{assembly-code emitters}\endmoddef ! 223: val address = ref 0 (* address of next instruction in words *) ! 224: \LA{}real number state info and \code{}decode_real_ptr\edoc{}\RA{} ! 225: fun MipsAsm stream = ! 226: let fun say s = (output stream s; flush_out stream) ! 227: fun printaddr addrref = ! 228: let val n = !addrref ! 229: in (if n<10 then " " else if n < 100 then " " else "") ! 230: ^ (Integer.makestring n) ! 231: end ! 232: local ! 233: open Bits ! 234: fun hexdigit n = ! 235: let val d = andb(n,15) ! 236: in if d <= 9 then chr(d+ord("0")) ! 237: else chr(d-10+ord("a")) ! 238: end ! 239: fun hex1 n = hexdigit(rshift(n,4))^hexdigit(n) ! 240: fun hex2 n = hex1(rshift(n,8))^hex1(n) ! 241: fun hex4 n = hex2(rshift(n,16))^hex2(n) ! 242: in ! 243: fun hex(hi,lo) = hex2(hi) ^ hex2(lo) ! 244: fun printaddr addrref = ! 245: let val n = 4 * (!addrref) (* address in bytes *) ! 246: in "0x" ^ (hex4 n) ! 247: end ! 248: end ! 249: fun decode x = ( ! 250: say ((printaddr address) ^ ": (" ^ (hex x) ^") " ! 251: ^ (MipsDecode.decode x)); ! 252: address := !address + 1; () ! 253: ) ! 254: fun do_decode_real(w,s) = ( ! 255: say ((printaddr address) ^ ": (" ^ (hex w) ^") " ! 256: ^ s ^ "\\n"); ! 257: address := !address + 1; () ! 258: ) ! 259: fun decode_real s = (real_string := s; AsmReal.realconst s) ! 260: fun decode_string n s = ! 261: if n > 0 then ! 262: (say ((printaddr address) ! 263: ^ ": \\"" ^substring(s,0,4) ^"\\"\\n"); ! 264: address := !address + 1; ! 265: decode_string (n-4) (substring(s,4,String.length(s)-4)) ! 266: ) ! 267: else () ! 268: in ! 269: decode_real_ptr := SOME do_decode_real; ! 270: (decode,decode_string,decode_real) : emitter_triple ! 271: end ! 272: \endcode ! 273: \begincode{13} ! 274: \moddef{real number state info and \code{}decode_real_ptr\edoc{}}\endmoddef ! 275: val decode_real_ptr = ref NONE : ((int * int) * string -> unit) option ref ! 276: (* used to emit asm code for a real word *) ! 277: ! 278: val real_least = ref NONE : (int * int) option ref ! 279: (* least significant word of real *) ! 280: val real_string = ref "" ! 281: fun emit_real_word w = ! 282: let val decode_real = case !decode_real_ptr of ! 283: SOME f => f ! 284: | NONE => ErrorMsg.impossible "missed real decoder in mips asm" ! 285: in ! 286: case !real_least of ! 287: NONE => real_least := SOME w ! 288: | SOME least => ! 289: (decode_real(least,"[low word of "^(!real_string)^"]"); ! 290: decode_real(w,"[high word of "^(!real_string)^"]")) ! 291: end ! 292: ! 293: structure AsmReal = MipsReal(struct val emit_word = emit_real_word end) ! 294: ! 295: \endcode ! 296: \filename{mipsreal.nw} ! 297: \begindocs{0} ! 298: \subsection{Handling IEEE floating point constants} ! 299: Here we take care of converting floating point constants from ! 300: string representation to 64-bit IEEE representation. ! 301: We use the machinery developed for the Sparc by John Reppy. ! 302: ! 303: Reppy's functor accepts a simple structure with a single value, ! 304: \code{}emitWord : int -> unit\edoc{}, which emits a 16-bit word. ! 305: It produces a \code{}PRIMREAL\edoc{}. ! 306: When \code{}RealConst\edoc{} is applied to the result, it produces a ! 307: structure containing a single function, \code{}val realconst : string -> unit\edoc{}. ! 308: This function, when applied to a string, emits the four sixteen-bit words ! 309: of the IEEE representation, most significant first. ! 310: ! 311: Our job will be to convert this to something that emits the two 32-bit ! 312: words of the constant, least significant word first. ! 313: First, let's consider the state information that has to be retained ! 314: while the halfwords are being emitted, and functions that change that state. ! 315: \enddocs ! 316: \begincode{1} ! 317: \moddef{state info}\endmoddef ! 318: val halfwords = ref nil : int list ref (* halfwords already out *) ! 319: val count = ref 0 (* length of halfwords *) ! 320: fun reset_state () = (halfwords := nil; count := 0) ! 321: fun add_half h = (count := !count + 1; halfwords := h :: (!halfwords)) ! 322: ! 323: \endcode ! 324: \begincode{2} ! 325: \moddef{emitting a halfword}\endmoddef ! 326: fun emit_half h = ! 327: if !count = 3 then (emit_four (h::(!halfwords)); reset_state()) ! 328: else add_half h ! 329: ! 330: \endcode ! 331: \begindocs{3} ! 332: To emit the whole list, we have to emit the words, one at a time. ! 333: We use descriptive names to remind ourselves what is signficant ! 334: (highest is most significant). ! 335: \enddocs ! 336: \begincode{4} ! 337: \moddef{emitting four halfwords}\endmoddef ! 338: fun emit_four [lowest,low,high,highest] = ! 339: (emit_word(low,lowest);emit_word(highest,high)) ! 340: | emit_four _ = ErrorMsg.impossible "bad floating pt constant in mips" ! 341: ! 342: \endcode ! 343: \begindocs{5} ! 344: Now, we bundle up the whole thing in a functor that ! 345: gets passed a structure holding \code{}emit_word\edoc{} and returns ! 346: one containing \code{}realconst\edoc{}. ! 347: \enddocs ! 348: \begincode{6} ! 349: \moddef{*}\endmoddef ! 350: functor MipsReal(E: sig val emit_word : int * int -> unit end) : REALCONST = ! 351: struct ! 352: open E ! 353: \LA{}state info\RA{} ! 354: \LA{}emitting four halfwords\RA{} ! 355: \LA{}emitting a halfword\RA{} ! 356: structure IEEERealConst = ! 357: RealConst(IEEEReal(struct val emitWord = emit_half end)) ! 358: val realconst = IEEERealConst.realconst ! 359: end ! 360: ! 361: ! 362: ! 363: ! 364: \endcode ! 365: \filename{mips.nw} ! 366: \begindocs{0} ! 367: \section{Using \code{}MIPSCODER\edoc{} to implement a \code{}CMACHINE\edoc{}} ! 368: ! 369: \enddocs ! 370: \begincode{1} ! 371: \moddef{*}\endmoddef ! 372: functor MipsCM(MipsC : MIPSCODER) : CMACHINE = struct ! 373: ! 374: open MipsC System.Tags ! 375: ! 376: \LA{}utility functions\RA{} ! 377: ! 378: \LA{}immediate and register functions\RA{} ! 379: ! 380: \LA{}register definitions\RA{} ! 381: ! 382: \LA{}move\RA{} ! 383: \LA{}alignment, marks, and constants\RA{} ! 384: \LA{}labels\RA{} ! 385: \LA{}record manipulation\RA{} ! 386: \LA{}indexed fetch and store (byte)\RA{} ! 387: \LA{}indexed fetch and store (word)\RA{} ! 388: \LA{}arithmetic\RA{} ! 389: \LA{}shifts\RA{} ! 390: \LA{}arithmetic and shifts with overflow detection\RA{} ! 391: \LA{}bitwise operations\RA{} ! 392: \LA{}branches\RA{} ! 393: ! 394: \LA{}floating point\RA{} ! 395: ! 396: \LA{}memory check\RA{} ! 397: ! 398: \LA{}omitted functions\RA{} ! 399: ! 400: val comment = M.comment ! 401: ! 402: (* +DEBUG *) ! 403: \LA{}DEBUG code\RA{} ! 404: (* -DEBUG *) ! 405: ! 406: end (* MipsCM *) ! 407: ! 408: \endcode ! 409: \begindocs{2} ! 410: The debugging code replaces possibly offensive functions with functions ! 411: that diagnose their own exceptions. ! 412: \enddocs ! 413: \begincode{3} ! 414: \moddef{DEBUG code}\endmoddef ! 415: fun diag (s : string) f x = ! 416: f x handle e => ! 417: (print "?exception "; print (System.exn_name e); ! 418: print " in mips."; print s; print "\\n"; ! 419: raise e) ! 420: ! 421: \endcode ! 422: \begincode{4} ! 423: \moddef{immediate and register functions}\endmoddef ! 424: val immed = Immed ! 425: fun isimmed(Immed i) = SOME i ! 426: | isimmed _ = NONE ! 427: ! 428: fun isreg(Direct(Reg i)) = SOME i | isreg _ = NONE ! 429: fun eqreg (a: EA) b = a=b ! 430: ! 431: ! 432: \endcode ! 433: \begindocs{5} ! 434: Here's what our register conventions are: ! 435: \input regs ! 436: \enddocs ! 437: \begincode{6} ! 438: \moddef{register definitions}\endmoddef ! 439: val standardarg = Direct(Reg 2) ! 440: val standardcont = Direct(Reg 3) ! 441: val standardclosure = Direct(Reg 4) ! 442: val miscregs = map (Direct o Reg) [5,6,7,8,9,10,11,12,13,14, ! 443: 15,16,17,18,19] ! 444: val storeptr as Direct storeptr' = Direct(Reg 22) ! 445: val dataptr as Direct dataptr' = Direct(Reg 23) ! 446: val exnptr = Direct(Reg 30) ! 447: ! 448: (* internal use only *) ! 449: val my_arithtemp as Direct my_arithtemp'= Direct(Reg 20) ! 450: val my_ptrtemp as Direct my_ptrtemp' = Direct(Reg 21) ! 451: ! 452: (* exported for external use *) ! 453: val arithtemp as Direct arithtemp' = Direct(Reg 24) ! 454: val arithtemp2 as Direct arithtemp2'= Direct(Reg 25) ! 455: ! 456: \endcode ! 457: \begincode{7} ! 458: \moddef{move}\endmoddef ! 459: fun move (src,Direct dest) = M.move(src, dest) ! 460: | move _ = ErrorMsg.impossible "destination of move not register in mips" ! 461: \endcode ! 462: \begincode{8} ! 463: \moddef{alignment, marks, and constants}\endmoddef ! 464: val align = M.align ! 465: val mark = M.mark ! 466: ! 467: val emitlong = M.emitlong ! 468: val realconst = M.realconst ! 469: val emitstring = M.emitstring ! 470: ! 471: \endcode ! 472: \begincode{9} ! 473: \moddef{labels}\endmoddef ! 474: fun emitlab(i,Immedlab lab) = M.emitlab(i,lab) ! 475: | emitlab _ = ErrorMsg.impossible "bad emitlab arg in mips" ! 476: fun newlabel() = Immedlab(M.newlabel()) ! 477: fun define (Immedlab lab) = M.define lab ! 478: | define _ = ErrorMsg.impossible "bad define arg in mips" ! 479: \endcode ! 480: \begincode{10} ! 481: \moddef{DEBUG code}\endmoddef ! 482: val emitlab = diag "emitlab" emitlab ! 483: val define = diag "define" define ! 484: ! 485: ! 486: \endcode ! 487: \begindocs{11} ! 488: We only ever put the address of a newly created record into a register. ! 489: If I make this out correctly, the first word on the list of ! 490: values \code{}vl\edoc{} is actually a descriptor. ! 491: BUGS: The original routine put the address of the descriptor ! 492: into \code{}z\edoc{}. ! 493: What needs to go into \code{}z\edoc{} is the address of the first word in the record. ! 494: We can get this by adding 4 to the \code{}dataptr'\edoc{}. ! 495: \enddocs ! 496: \begincode{12} ! 497: \moddef{record manipulation}\endmoddef ! 498: fun record(vl, Direct z) = ! 499: let open CPS ! 500: val len = List.length vl ! 501: fun f(i,nil) = () ! 502: | f(i,(r, SELp(j,p))::rest) = (* follow ptrs to get the item *) ! 503: (M.lw(my_ptrtemp', r, j*4); f(i,(my_ptrtemp,p)::rest)) ! 504: | f(i,(Direct r,OFFp 0)::rest) = (* simple store, last first *) ! 505: (M.sw(r, dataptr, i*4); f(i-1,rest)) ! 506: | f(i,(Direct r, OFFp j)::rest) = ! 507: (M.add(r, Immed(4*j), my_ptrtemp'); ! 508: f(i,(my_ptrtemp,OFFp 0)::rest)) ! 509: | f(i,(ea,p)::rest) = (* convert to register-based *) ! 510: (M.move(ea, my_ptrtemp'); f(i,(my_ptrtemp,p)::rest)) ! 511: in f(len - 1, rev vl); (* store first word in \code{}0(dataptr')\edoc{} *) ! 512: M.add(dataptr', Immed 4, z); ! 513: M.add(dataptr', Immed(4*len), dataptr') ! 514: end ! 515: | record _ = ErrorMsg.impossible "result of record not register in mips" ! 516: ! 517: fun select(i, r, Direct s) = M.lw(s, r, i*4) ! 518: | select _ = ErrorMsg.impossible "result of select not register in mips" ! 519: ! 520: fun offset(i, Direct r, Direct s) = M.add(r,Immed(i*4), s) ! 521: | offset _ = ErrorMsg.impossible "nonregister arg to offset in mips" ! 522: \endcode ! 523: \begincode{13} ! 524: \moddef{DEBUG code}\endmoddef ! 525: val record = diag "record" record ! 526: val select = diag "select" select ! 527: val offset = diag "offset" offset ! 528: ! 529: \endcode ! 530: \begindocs{14} ! 531: For the indexed fetch and store, arithtemp is {\em not} tagged---the ! 532: tags are removed at a higher level (in {\tt generic.sml}). ! 533: These could be made faster for the case when they're called with immediate ! 534: constants as \code{}x\edoc{}. ! 535: \enddocs ! 536: \begincode{15} ! 537: \moddef{indexed fetch and store (byte)}\endmoddef ! 538: (* fetchindexb(x,y) fetches a byte: y <- mem[x+arithtemp] ! 539: y cannot be arithtemp *) ! 540: fun fetchindexb(x,Direct y) = ! 541: (M.add(arithtemp',x,my_arithtemp'); ! 542: M.lbu(y,my_arithtemp,0)) ! 543: | fetchindexb _ = ErrorMsg.impossible "fetchb result not register in mips" ! 544: ! 545: (* storeindexb(x,y) stores a byte: mem[y+arithtemp] <- x; *) ! 546: fun storeindexb(Direct x,y) = ! 547: (M.add(arithtemp',y,my_arithtemp'); ! 548: M.sb(x,my_arithtemp,0)) ! 549: | storeindexb _ = ErrorMsg.impossible "storeb arg not register in mips" ! 550: ! 551: (* jmpindexb(x) pc <- (x+arithtemp) *) ! 552: fun jmpindexb x = (M.add(arithtemp',x,my_arithtemp'); ! 553: M.jump(my_arithtemp')) ! 554: ! 555: \endcode ! 556: \begincode{16} ! 557: \moddef{DEBUG code}\endmoddef ! 558: val fetchindexb = diag "fetchindexb" fetchindexb ! 559: val storeindexb = diag "storeindexb" storeindexb ! 560: val jmpindexb = diag "jmpindexb" jmpindexb ! 561: ! 562: ! 563: \endcode ! 564: \begindocs{17} ! 565: Here it looks like \code{}z\edoc{} is a tagged integer number of words, ! 566: so that \code{}2*(z-1)\edoc{} converts to the appropriate byte offset. ! 567: But I'm just guessing. ! 568: In any case, it saves an instruction to compute \code{}2*z\edoc{} (actually \code{}z+z\edoc{}) ! 569: and ! 570: load (or store) with offset \code{}~2\edoc{}. ! 571: ! 572: Anything stored with \code{}storeindexl\edoc{} is being put into an array, so it ! 573: is safe to treat it as a pointer. ! 574: \enddocs ! 575: \begincode{18} ! 576: \moddef{indexed fetch and store (word)}\endmoddef ! 577: (* fetchindexl(x,y,z) fetches a word: y <- mem[x+2*(z-1)] *) ! 578: (* storeindexl(x,y,z) stores a word: mem[y+2*(z-1)] <- x *) ! 579: ! 580: fun fetchindexl(x,Direct y, Direct z) = ! 581: (M.sll(Immed 1,z,my_arithtemp'); ! 582: M.add(my_arithtemp',x,my_arithtemp'); ! 583: M.lw(y, my_arithtemp,~2)) ! 584: | fetchindexl(x,Direct y, Immed z) = M.lw(y, x, z+z-2) ! 585: | fetchindexl _ = ErrorMsg.impossible "fetchl result not register in mips" ! 586: ! 587: fun storeindexl(Direct x,y, Immed 1) = M.sw(x,y,0) ! 588: | storeindexl(Direct x,y,Direct z) = ! 589: (M.sll(Immed 1,z,my_arithtemp'); ! 590: M.add(my_arithtemp',y,my_arithtemp'); ! 591: M.sw(x, my_arithtemp,~2)) ! 592: | storeindexl(Direct x,y,Immed z) = M.sw(x,y,z+z-2) ! 593: ! 594: | storeindexl(Direct _,_,Immedlab _) = ! 595: ErrorMsg.impossible "storeindexl(Direct _,_,Immedlab _) in mips" ! 596: ! 597: | storeindexl(Immedlab label,y,z) = ! 598: (M.move(Immedlab label,my_ptrtemp'); ! 599: storeindexl(my_ptrtemp,y,z)) ! 600: ! 601: | storeindexl(Immed constant,y,offset) = ! 602: (M.move(Immed constant,my_ptrtemp'); ! 603: storeindexl(my_ptrtemp,y,offset)) ! 604: ! 605: \endcode ! 606: \begincode{19} ! 607: \moddef{DEBUG code}\endmoddef ! 608: val fetchindexl = diag "fetchindexl" fetchindexl ! 609: val storeindexl = diag "storeindexl" storeindexl ! 610: ! 611: ! 612: \endcode ! 613: \begindocs{20} ! 614: The function \code{}three\edoc{} makes commutative three-operand ! 615: instructions easier to call. ! 616: All three operands become \code{}EA\edoc{}s, and it is enough if either of the ! 617: first two operands is a register. ! 618: \enddocs ! 619: \begincode{21} ! 620: \moddef{utility functions}\endmoddef ! 621: fun three f (Direct x, ea, Direct y) = f(x,ea,y) ! 622: | three f (ea, Direct x, Direct y) = f(x,ea,y) ! 623: | three f _ =ErrorMsg.impossible "neither arg to three f is register in mips" ! 624: ! 625: \endcode ! 626: \begindocs{22} ! 627: I assume that shifts are only ever done on arithmetic quantities, ! 628: not pointers, so that I am justified in using \code{}my_arithtemp'\edoc{} to ! 629: store intermediate values. This is consistent with being unwilling ! 630: to shift things matching \code{}Immedlab _\edoc{}. ! 631: Appel agrees that pointers aren't shifted, as far as he can remember. ! 632: \enddocs ! 633: \begincode{23} ! 634: \moddef{shifts}\endmoddef ! 635: fun ashr(shamt, Direct op1, Direct result) = M.sra(shamt,op1,result) ! 636: | ashr(shamt, Immed op1, Direct result) = ! 637: (M.move(Immed op1,my_arithtemp'); M.sra(shamt,my_arithtemp',result)) ! 638: | ashr _ = ErrorMsg.impossible "ashr args don't match in mips" ! 639: fun ashl(shamt, Direct op1, Direct result) = M.sll(shamt,op1,result) ! 640: | ashl(shamt, Immed op1, Direct result) = ! 641: (M.move(Immed op1,my_arithtemp'); M.sll(shamt,my_arithtemp',result)) ! 642: | ashl _ = ErrorMsg.impossible "ashl args don't match in mips" ! 643: \endcode ! 644: \begincode{24} ! 645: \moddef{DEBUG code}\endmoddef ! 646: val ashr = diag "ashr" ashr ! 647: val ashl = diag "ashl" ashl ! 648: ! 649: \endcode ! 650: \begincode{25} ! 651: \moddef{bitwise operations}\endmoddef ! 652: val orb = three M.or ! 653: val andb = three M.and' ! 654: fun notb (a,b) = subl3(a, Immed ~1, b) (* ~1 - a == one's complement *) ! 655: val xorb = three M.xor ! 656: \endcode ! 657: \begincode{26} ! 658: \moddef{DEBUG code}\endmoddef ! 659: val orb = diag "orb" orb ! 660: val andb = diag "andb" andb ! 661: val notb = diag "notb" notb ! 662: val xorb = diag "xorb" xorb ! 663: ! 664: ! 665: \endcode ! 666: \begindocs{27} ! 667: Subtraction may appear a bit odd. ! 668: The MIPS machine instruction and \code{}MIPSCODER.sub\edoc{} both subtract ! 669: their second operand from their first operand. ! 670: The VAX machine instruction and \code{}CMACHINE.subl3\edoc{} both subtract ! 671: their first operand from their second operand. ! 672: This will certainly lead to endless confusion. ! 673: \enddocs ! 674: \begincode{28} ! 675: \moddef{arithmetic}\endmoddef ! 676: val addl3 = three M.add ! 677: ! 678: fun subl3(Immed k, x, y) = addl3(x, Immed(~k), y) ! 679: | subl3(Direct x, Direct y, Direct z) = M.sub(y,x,z) ! 680: | subl3(x, Immed k, dest) = ! 681: (M.move(Immed k, my_arithtemp'); ! 682: subl3(x, my_arithtemp, dest)) ! 683: | subl3 _ = ErrorMsg.impossible "subl3 args don't match in mips" ! 684: ! 685: \endcode ! 686: \begindocs{29} ! 687: We assume that any quantities being multiplied are arithmetic ! 688: quantities, not pointers. ! 689: \enddocs ! 690: \begincode{30} ! 691: \moddef{arithmetic}\endmoddef ! 692: fun mull2(Direct x, Direct y) = M.mult(y,x,y) ! 693: | mull2(Immed x, Direct y) = (M.move(Immed x,my_arithtemp'); ! 694: M.mult(y,my_arithtemp',y)) ! 695: | mull2 _ = ErrorMsg.impossible "mull2 args don't match in mips" ! 696: fun divl2(Direct x, Direct y) = M.div(y,x,y) ! 697: | divl2(Immed x, Direct y) = (M.move(Immed x,my_arithtemp'); ! 698: M.div(y,my_arithtemp',y)) ! 699: | divl2 _ = ErrorMsg.impossible "divl2 args don't match in mips" ! 700: ! 701: \endcode ! 702: \begincode{31} ! 703: \moddef{DEBUG code}\endmoddef ! 704: val addl3 = diag "addl3" addl3 ! 705: val subl3 = diag "subl3" subl3 ! 706: val mull2 = diag "mull2" mull2 ! 707: val divl2 = diag "divl2" divl2 ! 708: ! 709: ! 710: \endcode ! 711: \begindocs{32} ! 712: The Mips hardware detects two's complement integer overflow on ! 713: add and subtract instructions only. ! 714: The exception is not maskable (see the Mips book, page 5-18). ! 715: At the moment we don't implement any overflow detection for multiplications ! 716: or for left shifts. ! 717: This has consequences only for coping with real constants and for ! 718: compiling user programs. ! 719: \enddocs ! 720: \begincode{33} ! 721: \moddef{arithmetic and shifts with overflow detection}\endmoddef ! 722: val addl3t = addl3 ! 723: val subl3t = subl3 ! 724: \endcode ! 725: \begindocs{34} ! 726: The Mips multiplies two 32-bit quantities to get a 64-bit result. ! 727: That result fits in 32 bits if and only if the high-order word is zero or ! 728: negative one, and it has the same sign as the low order word. ! 729: Thus, we can add the sign bit of the low order word to the high order ! 730: word, and we have overflow if and only if the result is nonzero. ! 731: \enddocs ! 732: \begincode{35} ! 733: \moddef{arithmetic and shifts with overflow detection}\endmoddef ! 734: fun mull2t(x,y as Direct y') = ! 735: let val ok = M.newlabel() ! 736: in mull2(x,y); ! 737: M.mfhi(my_arithtemp'); ! 738: M.slt(y',Direct (Reg 0),my_ptrtemp'); (* 0 or 1 OK in pointer *) ! 739: M.add(my_arithtemp',my_ptrtemp,my_arithtemp'); ! 740: M.beq(true,my_arithtemp',Reg 0,ok); (* OK if not overflow *) ! 741: M.lui(my_arithtemp',32767); ! 742: M.add(my_arithtemp',my_arithtemp,my_arithtemp'); (* overflows *) ! 743: M.define(ok) ! 744: end ! 745: | mull2t _ = ErrorMsg.impossible "result of mull2t not register in mips" ! 746: ! 747: \endcode ! 748: \begincode{36} ! 749: \moddef{DEBUG code}\endmoddef ! 750: val addl3t = diag "addl3t" addl3t ! 751: val subl3t = diag "subl3t" subl3t ! 752: val mull2t = diag "mull2t" mull2t ! 753: val ashlt = diag "ashlt" ashlt ! 754: ! 755: ! 756: \endcode ! 757: \begindocs{37} ! 758: We hack \code{}ibranch\edoc{} to make sure it will only reverse once. ! 759: It's easier than thinking. ! 760: \enddocs ! 761: \begincode{38} ! 762: \moddef{branches}\endmoddef ! 763: datatype condition = NEQ | EQL | LEQ | GEQ | LSS | GTR ! 764: local ! 765: fun makeibranch reverse = ! 766: let ! 767: fun ibranch (cond, Immed a, Immed b, Immedlab label) = ! 768: if (case cond of EQL => a=b | NEQ => a<>b | LSS => a<b | ! 769: LEQ => a<=b | GTR => a>b | GEQ => a>=b) ! 770: then M.beq(true,Reg 0, Reg 0, label) else () ! 771: | ibranch (NEQ, Direct r, Direct s, Immedlab label) = ! 772: M.beq(false, r, s, label) ! 773: | ibranch (NEQ, Direct r, x, Immedlab label) = ! 774: (M.move(x, my_arithtemp'); ! 775: M.beq(false, r, my_arithtemp', label)) ! 776: | ibranch (EQL, Direct r, Direct s, Immedlab label) = ! 777: M.beq(true, r, s, label) ! 778: | ibranch (EQL, Direct r, x, Immedlab label) = ! 779: (M.move(x, my_arithtemp'); ! 780: M.beq(true, r, my_arithtemp', label)) ! 781: | ibranch (LSS, Direct r, x, Immedlab lab) = ! 782: (M.slt(r,x,my_arithtemp'); ! 783: M.beq(false,Reg 0, my_arithtemp',lab)) ! 784: | ibranch (GEQ, Direct r, x, Immedlab lab) = ! 785: (M.slt(r,x,my_arithtemp'); ! 786: M.beq(true,Reg 0, my_arithtemp',lab)) ! 787: | ibranch (GTR, x, Direct r, Immedlab lab) = ! 788: (M.slt(r,x,my_arithtemp'); ! 789: M.beq(false,Reg 0, my_arithtemp',lab)) ! 790: | ibranch (LEQ, x, Direct r, Immedlab lab) = ! 791: (M.slt(r,x,my_arithtemp'); ! 792: M.beq(true,Reg 0, my_arithtemp',lab)) ! 793: (* These two cases added to prevent infinite reversal *) ! 794: | ibranch (GTR, Direct r, x, Immedlab lab) = ! 795: (M.move(x, my_arithtemp'); ! 796: M.slt(my_arithtemp',Direct r,my_arithtemp'); ! 797: M.beq(false,Reg 0,my_arithtemp',lab)) ! 798: | ibranch (LEQ, Direct r, x, Immedlab lab) = ! 799: (M.move(x, my_arithtemp'); ! 800: M.slt(my_arithtemp',Direct r,my_arithtemp'); ! 801: M.beq(true,Reg 0,my_arithtemp',lab)) ! 802: | ibranch (_, Immedlab _, Immedlab _, _) = ! 803: ErrorMsg.impossible "bad ibranch args 1 in mips" ! 804: | ibranch (_, Immedlab _, _, _) = ! 805: ErrorMsg.impossible "bad ibranch args 1a in mips" ! 806: | ibranch (_, _, Immedlab _, _) = ! 807: ErrorMsg.impossible "bad ibranch args 1b in mips" ! 808: | ibranch (_, _, _, Direct _) = ! 809: ErrorMsg.impossible "bad ibranch args 2 in mips" ! 810: | ibranch (_, _, _, Immed _) = ! 811: ErrorMsg.impossible "bad ibranch args 3 in mips" ! 812: | ibranch (cond, x, y, l) = ! 813: let fun rev LEQ = GEQ ! 814: | rev GEQ = LEQ ! 815: | rev LSS = GTR ! 816: | rev GTR = LSS ! 817: | rev NEQ = NEQ ! 818: | rev EQL = EQL ! 819: in if reverse then (makeibranch false) (rev cond, y,x,l) ! 820: else ErrorMsg.impossible "infinite ibranch reversal in mips" ! 821: ! 822: end ! 823: in ibranch ! 824: end ! 825: in ! 826: val ibranch = makeibranch true ! 827: end ! 828: ! 829: \endcode ! 830: \begincode{39} ! 831: \moddef{branches}\endmoddef ! 832: fun jmp (Direct r) = M.jump(r) ! 833: | jmp (Immedlab lab) = M.beq(true,Reg 0,Reg 0,lab) ! 834: | jmp (Immed i) = ErrorMsg.impossible "jmp (Immed i) in mips" ! 835: ! 836: ! 837: (* branch on bit set *) ! 838: fun bbs (Immed k, Direct y, Immedlab label) = ! 839: (M.and'(y,Immed (Bits.lshift(1,k)),my_arithtemp'); ! 840: M.beq(false,my_arithtemp',Reg 0,label)) ! 841: | bbs _ = ErrorMsg.impossible "bbs args don't match in mips" ! 842: ! 843: \endcode ! 844: \begincode{40} ! 845: \moddef{DEBUG code}\endmoddef ! 846: val ibranch = diag "ibranch" ibranch ! 847: val jmp = diag "jmp" jmp ! 848: val bbs = diag "bbs" bbs ! 849: ! 850: \endcode ! 851: \begindocs{41} ! 852: We decided not to include floating point registers in our galaxy of ! 853: effective addresses. ! 854: This means that floating point registers are used only at this level, and ! 855: only to contain intermediate results. ! 856: All operands and final results will be stored in memory, in the usual ! 857: ML format (i.e. as 8-byte strings). ! 858: ! 859: In fact, we can be much more strict than that, and claim that ! 860: all floating point operands will live in FPR0 and FPR2, and that all ! 861: results will appear in FPR0. ! 862: ! 863: We don't make a distinction between general-purpose and floating point ! 864: registers; it's up to the instructions to know the difference. ! 865: \enddocs ! 866: \begincode{42} ! 867: \moddef{floating point}\endmoddef ! 868: val floatop1 = Reg 0 ! 869: val floatop2 = Reg 2 ! 870: val floatresult = Reg 0 ! 871: ! 872: \endcode ! 873: \begindocs{43} ! 874: One very common operation is to take the result of a floating point ! 875: operation and put it into a fresh record, newly allocated on the heap. ! 876: This operation is traditionally called \code{}finish_real\edoc{}, and it takes one ! 877: argument, the destination register for the new value. ! 878: All real values on the heap are labelled as 8-byte strings. ! 879: To store a floating point, we store the least significant ! 880: word in the lower address, but we store the most significant word ! 881: first, in case that triggers a garbage collection. ! 882: \enddocs ! 883: \begincode{44} ! 884: \moddef{floating point}\endmoddef ! 885: val real_tag = Immed(8*System.Tags.power_tags + System.Tags.tag_string) ! 886: ! 887: fun store_float(Reg n,ea,offset) = ! 888: if n mod 2 <> 0 then ErrorMsg.impossible "bad float reg in mips" ! 889: else (M.swc1(Reg (n+1),ea,offset+4);M.swc1(Reg n,ea,offset)) ! 890: ! 891: fun finish_real (Direct result) = ( ! 892: store_float(floatresult,dataptr,4); ! 893: M.move(real_tag,my_arithtemp'); ! 894: M.sw(my_arithtemp',dataptr,0); ! 895: M.add(dataptr',Immed 4,result); ! 896: M.add(dataptr',Immed 12,dataptr')) ! 897: | finish_real _ = ! 898: ErrorMsg.impossible "ptr to result of real operation not register in mips" ! 899: ! 900: \endcode ! 901: \begindocs{45} ! 902: Loading a floating point quantity is analogous. ! 903: \enddocs ! 904: \begincode{46} ! 905: \moddef{floating point}\endmoddef ! 906: fun load_float(Reg dest,src,offset) = ! 907: if dest mod 2 <> 0 then ErrorMsg.impossible "bad float reg in mips" ! 908: else (M.lwc1(Reg dest,src,offset); M.lwc1(Reg (dest+1),src,offset+4)) ! 909: ! 910: \endcode ! 911: \begindocs{47} ! 912: Now we can do a general two- and three-operand floating point operationa. ! 913: The only parameter is the function in \code{}MipsCoder\edoc{} that ! 914: emits the floating point register operation. ! 915: \enddocs ! 916: \begincode{48} ! 917: \moddef{floating point}\endmoddef ! 918: fun two_float instruction (op1,result) = ( ! 919: load_float(floatop1,op1,0); ! 920: instruction(floatop1,floatresult); ! 921: finish_real(result)) ! 922: ! 923: fun three_float instruction (op1,op2,result) = ( ! 924: load_float(floatop1,op1,0); ! 925: load_float(floatop2,op2,0); ! 926: instruction(floatop1,floatop2,floatresult); ! 927: finish_real(result)) ! 928: ! 929: \endcode ! 930: \begindocs{49} ! 931: That takes care of everything except branch ! 932: \enddocs ! 933: \begincode{50} ! 934: \moddef{floating point}\endmoddef ! 935: val mnegg = two_float M.neg_double ! 936: val mulg3 = three_float M.mul_double ! 937: val divg3 = three_float M.div_double ! 938: val addg3 = three_float M.add_double ! 939: val subg3 = three_float M.sub_double ! 940: ! 941: ! 942: \endcode ! 943: \begindocs{51} ! 944: The Mips doesn't provide all six comparisons in hardware, so the ! 945: next function does the comparison using only less than and equal. ! 946: The result tells \code{}bcop1\edoc{} whether to branch on condition true ! 947: or condition false. ! 948: \enddocs ! 949: \begincode{52} ! 950: \moddef{floating point compare}\endmoddef ! 951: fun compare(LSS,op1,op2) = (M.slt_double(op1,op2); true) ! 952: | compare(GEQ,op1,op2) = (M.slt_double(op1,op2); false) ! 953: | compare(EQL,op1,op2) = (M.seq_double(op1,op2); true) ! 954: | compare(NEQ,op1,op2) = (M.seq_double(op1,op2); false) ! 955: | compare(LEQ,op1,op2) = compare(GEQ,op2,op1) ! 956: | compare(GTR,op1,op2) = compare(LSS,op2,op1) ! 957: \endcode ! 958: \begincode{53} ! 959: \moddef{floating point}\endmoddef ! 960: local ! 961: \LA{}floating point compare\RA{} ! 962: in ! 963: fun gbranch (cond, op1, op2, Immedlab label) = ( ! 964: load_float(floatop1,op1,0); ! 965: load_float(floatop2,op2,0); ! 966: M.bcop1(compare(cond,floatop1,floatop2),label)) ! 967: | gbranch _ = ErrorMsg.impossible "insane gbranch target in mips.nw" ! 968: end ! 969: ! 970: ! 971: \endcode ! 972: \begindocs{54} ! 973: When a function begins execution, it checks to make sure there is sufficient ! 974: memory available that it can do all its allocation. ! 975: generic does this by calling \code{}checkLimit : int -> unit\edoc{}. ! 976: At the moment, we implement this check by doing a store, ! 977: taking advantage of the virtual memory hardware, which will cause an exception ! 978: if there's not enough memory. ! 979: Later we will replace this store with a check against a limit register, ! 980: which will avoid virtual memory hacking and which will have advantages ! 981: for concurrency. ! 982: \enddocs ! 983: \begincode{55} ! 984: \moddef{memory check}\endmoddef ! 985: fun checkLimit max_allocation = M.sw(Reg 0, dataptr, max_allocation-4) ! 986: (* store zero in last location to be used *) ! 987: ! 988: \endcode ! 989: \begindocs{56} ! 990: These two functions have null implementations. ! 991: \code{}beginStdFn\edoc{} is necessary only on the SPARC, since that machine needs to get ! 992: its program counter, and it is awkward to do so in the middle of a function. ! 993: ! 994: \code{}profile\edoc{} is a mysterious relic. ! 995: \enddocs ! 996: \begincode{57} ! 997: \moddef{omitted functions}\endmoddef ! 998: fun beginStdFn _ = () (* do nothing, just like the Vax *) ! 999: ! 1000: fun profile(i,incr) = () ! 1001: ! 1002: \endcode ! 1003: \filename{mipscoder.nw} ! 1004: \begindocs{0} ! 1005: \input verbatim ! 1006: \input itemize ! 1007: \chapter{A small assembler for the MIPS} ! 1008: This is part of the code generator for Standard ML of New Jersey. ! 1009: We generate code in several stages. ! 1010: This is nearly the lowest stage; it is like an assembler. ! 1011: The user can call any function in the MIPSCODER signature. ! 1012: Each one corresponds to an assembler pseudo-instruction. ! 1013: Most correspond to single MIPS instructions. ! 1014: The assembler remembers all the instructions that have been ! 1015: requested, and when \code{}codegen\edoc{} is called it generates MIPS ! 1016: code for them. ! 1017: ! 1018: Some other structure will be able to use the MIPS structure to implement ! 1019: a \code{}CMACHINE\edoc{}, which is the abstract machine that ML thinks it is running ! 1020: on. ! 1021: (What really happens is a functor maps some structure ! 1022: implementing \code{}MIPSCODER\edoc{} to a different structure implementing ! 1023: \code{}CMACHINE\edoc{}.) ! 1024: ! 1025: {\em Any function using a structure of this signature must avoid ! 1026: touching registers 1~and~31. ! 1027: Those registers are reserved for use by the assembler.} ! 1028: ! 1029: \enddocs ! 1030: \begindocs{1} ! 1031: Here is the signature of the assembler, \code{}MIPSCODER\edoc{}. ! 1032: It can be extracted from this file by ! 1033: $$\hbox{\tt notangle mipsinstr.nw -Rsignature}.$$ ! 1034: \enddocs ! 1035: \begincode{2} ! 1036: \moddef{signature}\endmoddef ! 1037: signature MIPSCODER = sig ! 1038: ! 1039: (* Assembler for the MIPS chip *) ! 1040: ! 1041: eqtype Label ! 1042: datatype Register = Reg of int ! 1043: (* Registers 1 and 31 are reserved for use by this assembler *) ! 1044: datatype EA = Direct of Register | Immed of int | Immedlab of Label ! 1045: (* effective address *) ! 1046: ! 1047: structure M : sig ! 1048: ! 1049: (* Emit various constants into the code *) ! 1050: ! 1051: val emitstring : string -> unit (* put a literal string into the ! 1052: code (null-terminated?) and ! 1053: extend with nulls to 4-byte ! 1054: boundary. Just chars, no ! 1055: descriptor or length *) ! 1056: val realconst : string -> unit (* emit a floating pt literal *) ! 1057: (* NOT RIGHT YET *) ! 1058: val emitlong : int -> unit (* emit a 4-byte integer literal *) ! 1059: ! 1060: ! 1061: (* Label bindings and emissions *) ! 1062: ! 1063: val newlabel : unit -> Label (* new, unbound label *) ! 1064: val define : Label -> unit (* cause the label to be bound to ! 1065: the code about to be generated *) ! 1066: val emitlab : int * Label -> unit (* L3: emitlab(k,L2) is equivalent to ! 1067: L3: emitlong(k+L2-L3) *) ! 1068: ! 1069: (* Control flow instructions *) ! 1070: ! 1071: val slt : Register * EA * Register -> unit ! 1072: (* (operand1, operand2, result) *) ! 1073: (* set less than family *) ! 1074: val beq : bool * Register * Register * Label -> unit ! 1075: (* (beq or bne, operand1, operand2, branch address) *) ! 1076: (* branch equal/not equal family *) ! 1077: ! 1078: val jump : Register -> unit (* jump register instruction *) ! 1079: ! 1080: val slt_double : Register * Register -> unit ! 1081: (* floating pt set less than *) ! 1082: val seq_double : Register * Register -> unit ! 1083: (* floating pt set equal *) ! 1084: val bcop1 : bool * Label -> unit (* floating pt conditional branch *) ! 1085: ! 1086: ! 1087: (* Arithmetic instructions *) ! 1088: (* arguments are (operand1, operand2, result) *) ! 1089: ! 1090: val add : Register * EA * Register -> unit ! 1091: val and' : Register * EA * Register -> unit ! 1092: val or : Register * EA * Register -> unit ! 1093: val xor : Register * EA * Register -> unit ! 1094: val sub : Register * Register * Register -> unit ! 1095: val div : Register * Register * Register -> unit ! 1096: val mult : Register * Register * Register -> unit ! 1097: val mfhi : Register -> unit (* high word of 64-bit multiply *) ! 1098: ! 1099: (* Floating point arithmetic *) ! 1100: ! 1101: val neg_double : Register * Register -> unit ! 1102: val mul_double : Register * Register * Register -> unit ! 1103: val div_double : Register * Register * Register -> unit ! 1104: val add_double : Register * Register * Register -> unit ! 1105: val sub_double : Register * Register * Register -> unit ! 1106: ! 1107: (* Move pseudo-instruction : move(src,dest) *) ! 1108: ! 1109: val move : EA * Register -> unit ! 1110: ! 1111: (* Load and store instructions *) ! 1112: (* arguments are (destination, source address, offset) *) ! 1113: ! 1114: val lbu : Register * EA * int -> unit (* bytes *) ! 1115: val sb : Register * EA * int -> unit ! 1116: val lw : Register * EA * int -> unit (* words *) ! 1117: val sw : Register * EA * int -> unit ! 1118: val lwc1: Register * EA * int -> unit (* floating point coprocessor *) ! 1119: val swc1: Register * EA * int -> unit ! 1120: val lui : Register * int -> unit ! 1121: ! 1122: (* Shift instructions *) ! 1123: (* arguments are (shamt, operand, result) *) ! 1124: (* shamt as Immedlab _ is senseless *) ! 1125: ! 1126: val sll : EA * Register * Register -> unit ! 1127: val sra : EA * Register * Register -> unit ! 1128: ! 1129: ! 1130: (* Miscellany *) ! 1131: ! 1132: val align : unit -> unit (* cause next data to be emitted on ! 1133: a 4-byte boundary *) ! 1134: val mark : unit -> unit (* emit a back pointer, ! 1135: also called mark *) ! 1136: ! 1137: val comment : string -> unit ! 1138: ! 1139: end (* signature of structure M *) ! 1140: ! 1141: val codegen : (int * int -> unit) * (int -> string -> unit) ! 1142: * (string -> unit) -> unit ! 1143: ! 1144: val codestats : outstream -> unit (* write statistics on stream *) ! 1145: ! 1146: end (* signature MIPSCODER *) ! 1147: \endcode ! 1148: \begindocs{3} ! 1149: The basic strategy of the implementation is to hold on, via the \code{}kept\edoc{} ! 1150: pointer, to the list of instructions generated so far. ! 1151: We use \code{}instr\edoc{} for the type of an instruction, so ! 1152: \code{}kept\edoc{} has type \code{}instr list ref\edoc{}. ! 1153: ! 1154: The instructions will be executed in the following order: the ! 1155: instruction at the head of the \code{}!kept\edoc{} is executed last. ! 1156: This enables us to accept calls in the order of execution but ! 1157: add the new instruction(s) to the list in constant time. ! 1158: ! 1159: ! 1160: \enddocs ! 1161: \begindocs{4} ! 1162: ! 1163: We structure the instruction stream a little bit by factoring ! 1164: out the difference between multiplication and division; these ! 1165: operations are treated identically in that the result has to be ! 1166: fetched out of the MIPS' LO register. ! 1167: ! 1168: We also factor the different of load and store instructions that can ! 1169: occur: we have load byte, load word, and load to coprocessor (floating point). ! 1170: \enddocs ! 1171: \begincode{5} ! 1172: \moddef{types auxiliary to \code{}instr\edoc{}}\endmoddef ! 1173: datatype size = Byte | Word | Floating ! 1174: datatype muldiv = MULT | DIV ! 1175: \endcode ! 1176: \begindocs{6} ! 1177: ! 1178: Here are the instructions that exist. ! 1179: We list them in more or less the order of the MIPSCODER signature. ! 1180: \enddocs ! 1181: \begincode{7} ! 1182: \moddef{definition of \code{}instr\edoc{}}\endmoddef ! 1183: \LA{}types auxiliary to \code{}instr\edoc{}\RA{} ! 1184: ! 1185: datatype instr = ! 1186: STRINGCONST of string (* constants *) ! 1187: | REALCONST of string ! 1188: | EMITLONG of int ! 1189: ! 1190: | DEFINE of Label (* labels *) ! 1191: | EMITLAB of int * Label ! 1192: ! 1193: | SLT of Register * EA * Register (* control flow *) ! 1194: | BEQ of bool * Register * Register * Label ! 1195: | JUMP of Register ! 1196: | SLT_D of Register * Register ! 1197: | SEQ_D of Register * Register ! 1198: | BCOP1 of bool * Label ! 1199: ! 1200: | NOP (* no-op for delay slot *) ! 1201: ! 1202: | ADD of Register * EA * Register (* arithmetic *) ! 1203: | AND of Register * EA * Register ! 1204: | OR of Register * EA * Register ! 1205: | XOR of Register * EA * Register ! 1206: | SUB of Register * Register * Register ! 1207: | MULDIV of muldiv * Register * Register ! 1208: | MFLO of Register (* mflo instruction used with ! 1209: 64-bit multiply and divide *) ! 1210: | MFHI of Register ! 1211: ! 1212: | NEG_D of Register * Register ! 1213: | MUL_D of Register * Register * Register ! 1214: | DIV_D of Register * Register * Register ! 1215: | ADD_D of Register * Register * Register ! 1216: | SUB_D of Register * Register * Register ! 1217: ! 1218: | MOVE of EA * Register (* put something into a register *) ! 1219: | LDI_32 of int * Register (* load in a big immediate constant (>16 bits) *) ! 1220: | LUI of Register * int (* Mips lui instruction *) ! 1221: ! 1222: | LOAD of size * Register * EA * int (* load and store *) ! 1223: | STORE of size * Register * EA * int ! 1224: ! 1225: | SLL of EA * Register * Register (* shift *) ! 1226: | SRA of EA * Register * Register ! 1227: ! 1228: | COMMENT of string (* generates nothing *) ! 1229: | MARK (* a backpointer *) ! 1230: \endcode ! 1231: \begindocs{8} ! 1232: ! 1233: Here is the code that handles the generated stream, \code{}kept\edoc{}. ! 1234: It begins life as \code{}nil\edoc{} and returns to \code{}nil\edoc{} every time code is ! 1235: generated. ! 1236: The function \code{}keep\edoc{} is a convenient way of adding a single \code{}instr\edoc{} to ! 1237: the list; it's very terse. ! 1238: Sometimes we have to add multiple \code{}instr\edoc{}s; then we use \code{}keeplist\edoc{}. ! 1239: We also define a function \code{}delay\edoc{} that is just like a \code{}keep\edoc{} but ! 1240: it adds a NOP in the delay slot. ! 1241: \enddocs ! 1242: \begincode{9} ! 1243: \moddef{instruction stream and its functions}\endmoddef ! 1244: val kept = ref nil : instr list ref ! 1245: fun keep f a = kept := f a :: !kept ! 1246: fun delay f a = kept := NOP :: f a :: !kept ! 1247: fun keeplist l = kept := l @ !kept ! 1248: \endcode ! 1249: \begincode{10} ! 1250: \moddef{reinitialize \code{}kept\edoc{}}\endmoddef ! 1251: kept := nil ! 1252: \endcode ! 1253: \begindocs{11} ! 1254: ! 1255: \subsection{Exporting functions for \code{}MIPSCODER\edoc{}} ! 1256: We now know enough to implement most of the functions called for in ! 1257: \code{}MIPSCODER\edoc{}. ! 1258: We still haven't decided on an implementation of labels, ! 1259: and there is one subtlety in multiplication and division, ! 1260: but the rest is set. ! 1261: \enddocs ! 1262: \begincode{12} ! 1263: \moddef{\code{}MIPSCODER\edoc{} functions}\endmoddef ! 1264: val emitstring = keep STRINGCONST (* literals *) ! 1265: val realconst = keep REALCONST ! 1266: val emitlong = keep EMITLONG ! 1267: ! 1268: \LA{}label functions\RA{} (* labels *) ! 1269: ! 1270: val slt = keep SLT (* control flow *) ! 1271: val beq = delay BEQ ! 1272: val jump = delay JUMP ! 1273: val slt_double = delay SLT_D ! 1274: val seq_double = delay SEQ_D ! 1275: val bcop1 = delay BCOP1 ! 1276: ! 1277: val add = keep ADD (* arithmetic *) ! 1278: val and' = keep AND ! 1279: val or = keep OR ! 1280: val xor = keep XOR ! 1281: val op sub = keep SUB ! 1282: \LA{}multiplication and division functions\RA{} ! 1283: ! 1284: val neg_double = keep NEG_D ! 1285: val mul_double = keep MUL_D ! 1286: val div_double = keep DIV_D ! 1287: val add_double = keep ADD_D ! 1288: val sub_double = keep SUB_D ! 1289: ! 1290: val move = keep MOVE ! 1291: ! 1292: fun lbu (a,b,c) = delay LOAD (Byte,a,b,c) (* load and store *) ! 1293: fun lw (a,b,c) = delay LOAD (Word,a,b,c) ! 1294: fun lwc1 (a,b,c) = delay LOAD (Floating,a,b,c) ! 1295: fun sb (a,b,c) = keep STORE (Byte,a,b,c) ! 1296: fun sw (a,b,c) = keep STORE (Word,a,b,c) ! 1297: fun swc1 (a,b,c) = delay STORE (Floating,a,b,c) ! 1298: val lui = keep LUI ! 1299: ! 1300: val sll = keep SLL (* shift *) ! 1301: val sra = keep SRA ! 1302: ! 1303: fun align() = () (* never need to align on MIPS *) ! 1304: val mark = keep (fn () => MARK) ! 1305: val comment = keep COMMENT ! 1306: \endcode ! 1307: \begindocs{13} ! 1308: ! 1309: Multiplication and division have a minor complication; the ! 1310: result has to be fetched from the LO register. ! 1311: \enddocs ! 1312: \begincode{14} ! 1313: \moddef{multiplication and division functions}\endmoddef ! 1314: fun muldiv f (a,b,c) = keeplist [MFLO c, MULDIV (f,a,b)] ! 1315: val op div = muldiv DIV ! 1316: val mult = muldiv MULT ! 1317: val mfhi = keep MFHI ! 1318: \endcode ! 1319: \begindocs{15} ! 1320: ! 1321: For now, labels are just pointers to integers. ! 1322: During code generation, those integers will be set to positions ! 1323: in the instruction stream, and then they'll be useful as addresses ! 1324: relative to the program counter pointer (to be held in \code{}Reg pcreg\edoc{}). ! 1325: \enddocs ! 1326: \begincode{16} ! 1327: \moddef{definition of \code{}Label\edoc{}}\endmoddef ! 1328: type Label = int ref ! 1329: \endcode ! 1330: \begincode{17} ! 1331: \moddef{label functions}\endmoddef ! 1332: fun newlabel () = ref 0 ! 1333: val define = keep DEFINE ! 1334: val emitlab = keep EMITLAB ! 1335: \endcode ! 1336: \begindocs{18} ! 1337: ! 1338: Here's the overall plan of this structure: ! 1339: \enddocs ! 1340: \begincode{19} ! 1341: \moddef{*}\endmoddef ! 1342: structure MipsCoder : MIPSCODER = struct ! 1343: ! 1344: \LA{}definition of \code{}Label\edoc{}\RA{} ! 1345: ! 1346: datatype Register = Reg of int ! 1347: ! 1348: datatype EA = Direct of Register ! 1349: | Immed of int ! 1350: | Immedlab of Label ! 1351: ! 1352: \LA{}definition of \code{}instr\edoc{}\RA{} ! 1353: ! 1354: \LA{}instruction stream and its functions\RA{} ! 1355: ! 1356: structure M = struct ! 1357: \LA{}\code{}MIPSCODER\edoc{} functions\RA{} ! 1358: end ! 1359: ! 1360: open M ! 1361: ! 1362: \LA{}functions that assemble \code{}instr\edoc{}s into code\RA{} ! 1363: ! 1364: \LA{}statistics\RA{} ! 1365: ! 1366: end (* MipsInstr *) ! 1367: \endcode ! 1368: \begindocs{20} ! 1369: \subsection{Sizes of \code{}instr\edoc{}s} ! 1370: Now let's consider the correspondence between our \code{}instr\edoc{} type and the ! 1371: actual MIPS instructions we intend to emit. ! 1372: One important problem to solve is figuring out how big things are, ! 1373: so that we know what addresses to generate for the various labels. ! 1374: We will also want to know what address is currently stored in the program ! 1375: counter regsiter (\code{}pcreg\edoc{}), ! 1376: because we'll need to know when something is close ! 1377: enough that we can use a sixteen-bit address relative to that register. ! 1378: The kind of address we can use will determine how big things are. ! 1379: ! 1380: We'll rearrange the code so that we have a list of \code{}ref int * instr\edoc{} pairs, ! 1381: where the \code{}ref int\edoc{} stores the position in the list. ! 1382: (Positions start at zero.) ! 1383: Since in the MIPS all instructions are the same size, we measure ! 1384: position as number of instructions. ! 1385: While we're at it, we reverse the list so that the head will execute first, ! 1386: then the rest of the list. ! 1387: ! 1388: We begin with each position set to zero, and make a pass over the list ! 1389: trying to set the value of each position. ! 1390: We do this by estimating the size of (number of MIPS instructions ! 1391: generated for) each \code{}instr\edoc{}. ! 1392: Since there are forward references, we may not have all the distances right ! 1393: the first time, so we have to make a second pass. ! 1394: But during this second pass we could find that something is further ! 1395: away than we thought, and we have to switch from using a pc-relative mode to ! 1396: something else (or maybe grab the new pc?), which changes the size again, ! 1397: and moves things even further away. ! 1398: Because we can't control this process, we just keep making passes over the ! 1399: list until the process quiesces (we get the same size twice). ! 1400: ! 1401: In order to guarantee termination, we have to make sure later passes only ! 1402: increase the sizes of things. ! 1403: This is sufficient since there is a maximum number of MIPS instructions ! 1404: we can generate for each \code{}instr\edoc{}. ! 1405: ! 1406: ! 1407: While we're at it, we might want to complicate things by making the function ! 1408: that does the passes also emit code. ! 1409: For a single pass we hand an optional triple of emitters, the initial position, ! 1410: an \code{}int option\edoc{} for the program counter pointer (if known), and the ! 1411: instructions. ! 1412: ! 1413: ! 1414: ! 1415: I'm not sure what explains the use of the \code{}ref int\edoc{} to track the position, ! 1416: instead of just an \code{}int\edoc{}---it might be a desire to avoid the ! 1417: overhead of creating a bunch of new objects, or it might be really hard ! 1418: to do the passes cheaply. ! 1419: It should think a variation on \code{}map\edoc{} would do the job, but maybe I'm ! 1420: missing something. ! 1421: ! 1422: \enddocs ! 1423: \begindocs{21} ! 1424: \code{}emitters\edoc{} is actually a triple \code{}emit,emit_string,emit_real\edoc{}. ! 1425: \code{}emit : int * int -> unit\edoc{} emits one instruction, ! 1426: and \code{}emit_string : int -> string -> unit\edoc{} emits a string constant. ! 1427: \code{}emit_string\edoc{} could be specified as a function of \code{}emit\edoc{}, ! 1428: but the nature of the function would depend on whether the target ! 1429: machine was little-endian or big-endian, and we don't want to have ! 1430: that dependency built in. ! 1431: \code{}emit_real : string -> unit\edoc{} emits two words corresponding to an IEEE ! 1432: floating point constant in string form (e.g. \code{}"3.14159"\edoc{}). ! 1433: In principle, it can always be derived from \code{}emit_word\edoc{}, but it's ! 1434: easier to pass it in because then we can use John Reppy's code; ! 1435: see the \code{}MipsReal\edoc{} functor for more details, as well as ! 1436: \code{}mipsglue.sml\edoc{}. ! 1437: ! 1438: ! 1439: \code{}instrs\edoc{} is the ! 1440: list of instructions (in execute-head-last order). ! 1441: ! 1442: The second argument to \code{}pass\edoc{} indicates for what instructions code ! 1443: is to be generated. ! 1444: It is a record (position of next instruction, program counter pointer if any, ! 1445: remaining instructions to generate [with positions]). ! 1446: ! 1447: \indent \code{}prepare\edoc{} produces two results: the instruction stream with ! 1448: size pointers added, and the total size of code to be generated. ! 1449: We add the total size because that is the only way to find the number ! 1450: of \code{}bltzal\edoc{}s, which are implicit in the instruction stream. ! 1451: ! 1452: \enddocs ! 1453: \begincode{22} ! 1454: \moddef{assembler}\endmoddef ! 1455: fun prepare instrs = ! 1456: let fun add_positions(done, inst::rest) = ! 1457: add_positions( (ref 0, inst) :: done, rest) ! 1458: | add_positions(done, nil) = done ! 1459: ! 1460: val instrs' = add_positions(nil, instrs) (* reverse and add \code{}ref int\edoc{}s*) ! 1461: ! 1462: fun passes(oldsize) = ! 1463: (* make passes with no emission until size is stable*) ! 1464: let val size = pass NONE (0,NONE,instrs') ! 1465: in if size=oldsize then size ! 1466: else passes size ! 1467: end ! 1468: in \{size = passes 0, stream = instrs'\} ! 1469: end ! 1470: ! 1471: fun assemble emitters instrs = ! 1472: pass (SOME emitters) (0,NONE,#stream (prepare instrs)) ! 1473: ! 1474: \endcode ! 1475: \begincode{23} ! 1476: \moddef{functions that assemble \code{}instr\edoc{}s into code}\endmoddef ! 1477: fun get (SOME x) = x ! 1478: | get NONE = ErrorMsg.impossible "missing pcptr in mipscoder" ! 1479: ! 1480: \LA{}\code{}pcptr\edoc{} functions\RA{} ! 1481: \LA{}single pass\RA{} ! 1482: \LA{}assembler\RA{} ! 1483: ! 1484: fun codegen emitters = ( ! 1485: assemble emitters (!kept); ! 1486: \LA{}reinitialize \code{}kept\edoc{}\RA{} ! 1487: ) ! 1488: \endcode ! 1489: \begindocs{24} ! 1490: ! 1491: The program counter pointer is a device that enables us to to addressing ! 1492: relative to the pcp register, register 31. ! 1493: The need for it arises when we want to access a data element which we know ! 1494: only by its label. ! 1495: The labels give us addresses relative to the beginning of the function, ! 1496: but we can only use addresses relative to some register. ! 1497: The answer is to set register~31 with a \code{}bltzal\edoc{} instruction, ! 1498: then use that for addressing. ! 1499: ! 1500: The function \code{}needs_a_pcptr\edoc{} determines when it is necessary ! 1501: to have a known value in register~31. ! 1502: That is, we need the program counter pointer ! 1503: \itemize ! 1504: \item ! 1505: at \code{}NOP\edoc{} for a reason to be named later? ! 1506: \item ! 1507: at any operation that uses an effective address that refers to a label ! 1508: (since all labels have to be relative to the program counter). ! 1509: \item ! 1510: BEQ's and BCOP1's to very far away, ! 1511: since we have to compute the address for a JUMP ! 1512: knowing the value of the program counter pointer. ! 1513: \enditemize ! 1514: \enddocs ! 1515: \begincode{25} ! 1516: \moddef{\code{}pcptr\edoc{} functions}\endmoddef ! 1517: fun needs_a_pcptr(_,SLT(_,Immedlab _,_)) = true ! 1518: | needs_a_pcptr(_,ADD(_,Immedlab _,_)) = true ! 1519: | needs_a_pcptr(_,AND(_,Immedlab _,_)) = true ! 1520: | needs_a_pcptr(_,OR(_,Immedlab _,_)) = true ! 1521: | needs_a_pcptr(_,XOR(_,Immedlab _,_)) = true ! 1522: | needs_a_pcptr(_,MOVE(Immedlab _,_)) = true ! 1523: | needs_a_pcptr(_,LOAD(_,_,Immedlab _,_)) = true ! 1524: | needs_a_pcptr(_,STORE(_,_,Immedlab _,_)) = true ! 1525: | needs_a_pcptr(_,SLL(Immedlab _,_,_)) = true ! 1526: | needs_a_pcptr(_,SRA(Immedlab _,_,_)) = true ! 1527: | needs_a_pcptr(1, BEQ _) = false (* small BEQ's dont need pcptr *) ! 1528: | needs_a_pcptr(_, BEQ _) = true (* but large ones do *) ! 1529: | needs_a_pcptr(1, BCOP1 _) = false (* small BCOP1's dont need pcptr *) ! 1530: | needs_a_pcptr(_, BCOP1 _) = true (* but large ones do *) ! 1531: | needs_a_pcptr _ = false ! 1532: \endcode ! 1533: \begindocs{26} ! 1534: ! 1535: Creating the program counter pointer once, with a \code{}bltzal\edoc{}, is not ! 1536: enough; we have to invalidate the program counter pointer at every ! 1537: label, since control could arrive at the label from God knows where, and ! 1538: therefore we don't know what the program counter pointer is. ! 1539: ! 1540: We use the function \code{}makepcptr\edoc{} to create a new program counter pointer ! 1541: ``on the fly'' while generating code for other \code{}instrs\edoc{}. ! 1542: (I chose not to create a special \code{}instr\edoc{} for \code{}bltzal\edoc{}, which I ! 1543: could have inserted at appropriate points in the instruction stream.) ! 1544: To try and find an odd bug, I'm adding no-ops after each \code{}bltzal\edoc{}. ! 1545: I don't really believe they're necessary. ! 1546: ! 1547: The function \code{}gen\edoc{}, which generates the instructions (or computes ! 1548: their size), takes three arguments. ! 1549: Third: the list of instructions to be generated (paired with pointers ! 1550: to their sizes); first: the position (in words) at which to generate ! 1551: those instructions; second: the current value of the program counter ! 1552: pointer (register~31), if known. ! 1553: ! 1554: The mutual recursion between \code{}gen\edoc{} and \code{}makepcptr\edoc{} maintains ! 1555: the program counter pointer. ! 1556: \code{}gen\edoc{} invalidates it at labels, and calls \code{}makepcptr\edoc{} to create a valid ! 1557: one when necessary (as determined by \code{}needs_a_pcptr\edoc{}). ! 1558: \enddocs ! 1559: \begincode{27} ! 1560: \moddef{single pass}\endmoddef ! 1561: fun pass emitters = ! 1562: let fun makepcptr(i,x) = ! 1563: (* may need to emit NOP for delay slot if next instr is branch *) ! 1564: let val size = case x of ((_,BEQ _)::rest) => 2 ! 1565: | ((_,BCOP1 _)::rest) => 2 ! 1566: | _ => 1 ! 1567: in case emitters of NONE => () ! 1568: | SOME (emit, _, _ ) => ( ! 1569: emit(Opcodes.bltzal(0,0)); ! 1570: if size=2 then emit(Opcodes.add(0,0,0)) else ()); ! 1571: gen(i+size, SOME (i+2), x) ! 1572: end ! 1573: and gen(i,_,nil) = i ! 1574: | gen(i, _, (_,DEFINE lab) :: rest) = (lab := i; gen(i,NONE, rest)) ! 1575: (* invalidate the pc pointer at labels *) ! 1576: (* may want to do special fiddling with NOPs *) ! 1577: | gen(pos, pcptr, x as ((sizeref as ref size, inst) :: rest)) = ! 1578: if (pcptr=NONE andalso needs_a_pcptr(size, inst)) then makepcptr(pos,x) ! 1579: else case emitters of ! 1580: SOME (emit : int*int -> unit, emit_string : int -> string -> unit, ! 1581: emit_real : string -> unit) => ! 1582: \LA{}emit MIPS instructions\RA{} ! 1583: | NONE => ! 1584: \LA{}compute positions\RA{} ! 1585: in gen ! 1586: end ! 1587: ! 1588: \endcode ! 1589: \begindocs{28} ! 1590: \subsection{Generating the instructions} ! 1591: Now we need to consider the nitty-gritty details of just what instructions ! 1592: are generated for each \code{}instr\edoc{}. ! 1593: In early passes, we'll just need to know how many instructions are ! 1594: required (and that number may change from pass to pass, so it must be ! 1595: recomputed). ! 1596: In the last pass, the sizes are stable (by definition), so we can look ! 1597: at the sizes to see what instructions to generate. ! 1598: ! 1599: We'll consider the \code{}instrs\edoc{} in groups, but first, here's the ! 1600: way we will structure things: ! 1601: \enddocs ! 1602: \begincode{29} ! 1603: \moddef{compute positions}\endmoddef ! 1604: let \LA{}functions for computing sizes\RA{} ! 1605: val newsize = case inst of ! 1606: \LA{}cases for sizes to be computed\RA{} ! 1607: in if newsize > size then sizeref := newsize else (); ! 1608: gen(pos+(!sizeref) (* BUGS -- was pos+size*),pcptr,rest) ! 1609: end ! 1610: \endcode ! 1611: \begincode{30} ! 1612: \moddef{emit MIPS instructions}\endmoddef ! 1613: let fun gen1() = gen(pos+size,pcptr,rest) ! 1614: (* generate the rest of the \code{}instr\edoc{}s *) ! 1615: open Bits ! 1616: open Opcodes ! 1617: \LA{}declare reserved registers \code{}tempreg\edoc{} and \code{}pcreg\edoc{}\RA{} ! 1618: \LA{}functions for emitting instructions\RA{} ! 1619: in case inst of ! 1620: \LA{}cases of instructions to be emitted\RA{} ! 1621: end ! 1622: \endcode ! 1623: \begindocs{31} ! 1624: When we get around to generating code, we may need to use a temporary ! 1625: register. ! 1626: For example, if we want to load into a register ! 1627: an immediate constant that won't fit ! 1628: into 16~bits, we will have to load the high-order part of the constant ! 1629: with \code{}lui\edoc{}, then use \code{}addi\edoc{} to add then the low-order part. ! 1630: The MIPS assembler has a similar problem, and on page D-2 of ! 1631: the MIPS book we notice that register~1 is reserved for the use of the ! 1632: assembler. ! 1633: So we do the same. ! 1634: ! 1635: We need to reserve a second register for use in pointing to the program ! 1636: counter. ! 1637: We will use register 31 because the \code{}bltzal\edoc{} instruction automatically ! 1638: sets register 31 to the PC. ! 1639: \enddocs ! 1640: \begincode{32} ! 1641: \moddef{declare reserved registers \code{}tempreg\edoc{} and \code{}pcreg\edoc{}}\endmoddef ! 1642: val tempreg = 1 ! 1643: val pcreg = 31 ! 1644: \endcode ! 1645: \begindocs{33} ! 1646: ! 1647: Before showing the code for the actual instructions, we should ! 1648: point out that ! 1649: we have two different ways of emitting a long word. ! 1650: \code{}emitlong\edoc{} just splits the bits into two pieces for those cases ! 1651: when it's desirable to put a word into the memory image. ! 1652: \code{}split\edoc{} gives something that will load correctly ! 1653: when the high-order piece is loaded into a high-order halfword ! 1654: (using \code{}lui\edoc{}), ! 1655: and the low-order piece is sign-extended and then added to the ! 1656: high-order piece. ! 1657: This is the way we load immediate constants of more than sixteen bits. ! 1658: It is also useful for generating load or store instructions with ! 1659: offsets of more than sixteen bits: we \code{}lui\edoc{} the \code{}hi\edoc{} part and ! 1660: add it to the base regsiter, then use the \code{}lo\edoc{} part as an offset. ! 1661: \enddocs ! 1662: \begincode{34} ! 1663: \moddef{functions for emitting instructions}\endmoddef ! 1664: fun emitlong i = emit(rshift(i,16), andb(i,65535)) ! 1665: (* emit one long word (no sign fiddling) *) ! 1666: fun split i = let val hi = rshift(i,16) and lo = andb(i,65535) ! 1667: in if lo<32768 then (hi,lo) else (hi+1, lo-65536) ! 1668: end ! 1669: ! 1670: \endcode ! 1671: \begindocs{35} ! 1672: We begin implementing \code{}instrs\edoc{} by considering those that emit constants. ! 1673: String constants are padded with nulls out to a word boundary, and ! 1674: real constants take up two words. ! 1675: {\bf At the moment real constants seem to be zeros. ! 1676: One day this will have to be fixed.} ! 1677: Integer constants are just emitted with \code{}emitlong\edoc{}. ! 1678: \enddocs ! 1679: \begincode{36} ! 1680: \moddef{cases for sizes to be computed}\endmoddef ! 1681: STRINGCONST s => Integer.div(String.length(s)+3,4) ! 1682: | REALCONST _ => 2 ! 1683: | EMITLONG _ => 1 ! 1684: \endcode ! 1685: \begincode{37} ! 1686: \moddef{cases of instructions to be emitted}\endmoddef ! 1687: STRINGCONST s => ! 1688: let val s' = s ^ "\\000\\000\\000\\000" ! 1689: in gen1(emit_string (4*size) s') ! 1690: (* doesn't know Big vs Little-Endian *) ! 1691: end ! 1692: | REALCONST s => gen1(emit_real s) (* floating pt constant *) ! 1693: | EMITLONG i => gen1(emitlong i) ! 1694: \endcode ! 1695: \begindocs{38} ! 1696: ! 1697: Next consider the labels. ! 1698: A \code{}DEFINE\edoc{} should never reach this far, and \code{}EMITLAB\edoc{} is almost like ! 1699: an \code{}EMITLONG\edoc{}. ! 1700: \enddocs ! 1701: \begincode{39} ! 1702: \moddef{cases for sizes to be computed}\endmoddef ! 1703: | DEFINE _ => ErrorMsg.impossible "generate code for DEFINE in mipscoder" ! 1704: | EMITLAB _ => 1 ! 1705: \endcode ! 1706: \begincode{40} ! 1707: \moddef{cases of instructions to be emitted}\endmoddef ! 1708: | DEFINE _ => gen1(ErrorMsg.impossible "generate code for DEFINE in mipscoder") ! 1709: | EMITLAB(i, ref d) => gen1(emitlong((d-pos)*4+i)) ! 1710: \endcode ! 1711: \begindocs{41} ! 1712: ! 1713: Now we have to start worrying about instructions with \code{}EA\edoc{} in them. ! 1714: The real difficulty these things present is that they may have an ! 1715: immediate operand that won't fit in 16~bits. ! 1716: So we'll need to get this large immediate operand into a register, ! 1717: sixteen bits at a time, and then do the operation on the register. ! 1718: ! 1719: Since all of the arithmetic instructions have this difficulty, and since ! 1720: we can use them to implement the others, we'll start with those and ! 1721: catch up with the control-flow instructions later. ! 1722: \enddocs ! 1723: \begindocs{42} ! 1724: \code{}SUB\edoc{}, \code{}MULDIV\edoc{}, and \code{}MFLO\edoc{} all use registers only, so they are easy. ! 1725: The other arithmetic operations get treated exactly the same, so we'll ! 1726: use a function to compute the size. ! 1727: {\bf move this to follow the definition of \code{}arith\edoc{}?} ! 1728: \enddocs ! 1729: \begincode{43} ! 1730: \moddef{cases for sizes to be computed}\endmoddef ! 1731: | ADD(_, ea, _) => easize ea ! 1732: | AND(_, ea, _) => easize ea ! 1733: | OR (_, ea, _) => easize ea ! 1734: | XOR(_, ea, _) => easize ea ! 1735: | SUB _ => 1 ! 1736: | MULDIV _ => 1 ! 1737: | MFLO _ => 1 ! 1738: | MFHI _ => 1 ! 1739: \endcode ! 1740: \begindocs{44} ! 1741: Register operations take one instruction. ! 1742: Immediate operations take one instruction for 16~bit constants, ! 1743: and 3 for larger constants (since it costs two instructions to load ! 1744: a big immediate constant into a register). ! 1745: An immediate instruction with \code{}Immedlab l\edoc{} means that the operand ! 1746: is intended to be the machine address associated with that label. ! 1747: To compute that address, we need to add ! 1748: \code{}4*(l-pcptr)\edoc{} to the contents of ! 1749: register~\code{}pcreg\edoc{} (which holds \code{}4*pcptr\edoc{}), ! 1750: put the results in a register, and operate on that register. ! 1751: ! 1752: This tells us enough to compute the sizes. ! 1753: \enddocs ! 1754: \begincode{45} ! 1755: \moddef{functions for computing sizes}\endmoddef ! 1756: fun easize (Direct _) = 1 ! 1757: | easize (Immed i) = if abs(i)<32768 then 1 else 3 ! 1758: | easize (Immedlab(ref lab)) = 1 + easize(Immed (4*(lab-(get pcptr)))) ! 1759: \endcode ! 1760: \begindocs{46} ! 1761: ! 1762: As we have seen, ! 1763: to implement any arithmetic operation, we need to know the register ! 1764: form and the sixteen-bit immediate form. ! 1765: We will also want the operator from \code{}instr\edoc{}, since we do the ! 1766: large immediate via a recursive call. ! 1767: We'll set up a function, \code{}arith\edoc{}, that does the job. ! 1768: \enddocs ! 1769: \begincode{47} ! 1770: \moddef{functions for emitting instructions}\endmoddef ! 1771: fun arith (opr, rform, iform) = ! 1772: let fun ar (Reg op1, Direct (Reg op2), Reg result) = ! 1773: gen1(emit(rform(result,op1,op2))) ! 1774: | ar (Reg op1, Immed op2, Reg result) = ! 1775: (case size of ! 1776: 1 (* 16 bits *) => gen1(emit(iform(result,op1,op2))) ! 1777: | 3 (* 32 bits *) => ! 1778: gen(pos,pcptr, ! 1779: (ref 2, LDI_32(op2, Reg tempreg)):: ! 1780: (ref 1, opr(Reg op1, Direct(Reg tempreg), Reg result)):: ! 1781: rest) ! 1782: | _ => gen(ErrorMsg.impossible ! 1783: "bad size in arith Immed in mipscoder") ! 1784: ) ! 1785: | ar (Reg op1, Immedlab (ref op2), Reg result) = ! 1786: gen(pos, pcptr, ! 1787: (ref (size-1), ! 1788: ADD(Reg pcreg,Immed(4*(op2-(get pcptr))), Reg tempreg)):: ! 1789: (ref 1, opr(Reg op1, Direct(Reg tempreg), Reg result)):: ! 1790: rest) ! 1791: in ar ! 1792: end ! 1793: \endcode ! 1794: \begindocs{48} ! 1795: ! 1796: The generation itself may be a bit anticlimactic. ! 1797: The MIPS has no ``subtract immediate'' instruction, and \code{}SUB\edoc{} has ! 1798: a different type than the others, so we emit it directly. ! 1799: \enddocs ! 1800: \begincode{49} ! 1801: \moddef{cases of instructions to be emitted}\endmoddef ! 1802: | ADD stuff => arith (ADD,add,addi) stuff ! 1803: | AND stuff => arith (AND,and',andi) stuff ! 1804: | OR stuff => arith (OR,or,ori) stuff ! 1805: | XOR stuff => arith (XOR,xor,xori) stuff ! 1806: | SUB (Reg op1, Reg op2, Reg result) => gen1(emit(sub(result,op1,op2))) ! 1807: | MULDIV(DIV, Reg op1, Reg op2) => gen1(emit(div(op1,op2))) ! 1808: | MULDIV(MULT,Reg op1, Reg op2) => gen1(emit(mult(op1,op2))) ! 1809: | MFLO(Reg result) => gen1(emit(mflo(result))) ! 1810: | MFHI(Reg result) => gen1(emit(mfhi(result))) ! 1811: \endcode ! 1812: \begindocs{50} ! 1813: Floating point arithmetic is pretty easy because we always do it in ! 1814: registers. ! 1815: We also support only one format, double precision. ! 1816: \enddocs ! 1817: \begincode{51} ! 1818: \moddef{cases for sizes to be computed}\endmoddef ! 1819: | NEG_D _ => 1 ! 1820: | MUL_D _ => 1 ! 1821: | DIV_D _ => 1 ! 1822: | ADD_D _ => 1 ! 1823: | SUB_D _ => 1 ! 1824: \endcode ! 1825: \begindocs{52} ! 1826: When emitting instructions we have to remember the Mips instructions ! 1827: use result on the left, but the \code{}MIPSCODER\edoc{} signature requires result ! 1828: on the right. ! 1829: \enddocs ! 1830: \begincode{53} ! 1831: \moddef{cases of instructions to be emitted}\endmoddef ! 1832: | NEG_D (Reg op1,Reg result) => gen1(emit(neg_fmt(D_fmt,result,op1))) ! 1833: \endcode ! 1834: \begincode{54} ! 1835: \moddef{functions for emitting instructions}\endmoddef ! 1836: fun float3double instruction (Reg op1,Reg op2,Reg result) = ! 1837: gen1(emit(instruction(D_fmt,result,op1,op2))) ! 1838: \endcode ! 1839: \begincode{55} ! 1840: \moddef{cases of instructions to be emitted}\endmoddef ! 1841: | MUL_D x => float3double mul_fmt x ! 1842: | DIV_D x => float3double div_fmt x ! 1843: | ADD_D x => float3double add_fmt x ! 1844: | SUB_D x => float3double sub_fmt x ! 1845: ! 1846: ! 1847: \endcode ! 1848: \begindocs{56} ! 1849: We offer a separate \code{}MOVE\edoc{} instruction because of large immediate ! 1850: constants. ! 1851: It is always possible to do \code{}move(src,dest)\edoc{} by doing ! 1852: \code{}add(Reg 0,src,dest)\edoc{}, but the general form \code{}add(Reg i, Immed c, dest)\edoc{} ! 1853: takes three instructions when \code{}c\edoc{} is a large constant (more than 16 bits). ! 1854: Rather than clutter up the code for \code{}add\edoc{} (and \code{}or\edoc{} and \code{}xor\edoc{}) by ! 1855: trying to recognize register~0, we provide \code{}move\edoc{} explicitly. ! 1856: ! 1857: \indent \code{}LDI_32\edoc{} takes care of the particular case in which we are ! 1858: loading a 32-bit immediate constant into a register. ! 1859: It dates from the bad old days before \code{}MOVE\edoc{}, and it might be a good idea ! 1860: to remove it sometime. ! 1861: \enddocs ! 1862: \begincode{57} ! 1863: \moddef{functions for emitting instructions}\endmoddef ! 1864: fun domove (Direct (Reg src), Reg dest) = gen1(emit(add(dest,src,0))) ! 1865: | domove (Immed src, Reg dest) = ! 1866: (case size of ! 1867: 1 (* 16 bits *) => gen1(emit(addi(dest,0,src))) ! 1868: | 2 (* 32 bits *) => ! 1869: gen(pos,pcptr,(ref 2, LDI_32(src, Reg dest))::rest) ! 1870: | _ => gen(ErrorMsg.impossible "bad size in domove Immed in mipscoder") ! 1871: ) ! 1872: | domove (Immedlab (ref src), Reg dest) = ! 1873: gen(pos, pcptr, ! 1874: (ref size, ! 1875: ADD(Reg pcreg,Immed(4*(src-(get pcptr))), Reg dest))::rest) ! 1876: \endcode ! 1877: \begindocs{58} ! 1878: Notice we use \code{}easize\edoc{} and not \code{}movesize\edoc{} in the third clause ! 1879: because when we reach this point the treatment of a \code{}MOVE\edoc{} is the same ! 1880: as that of an \code{}ADD\edoc{}. ! 1881: \enddocs ! 1882: \begincode{59} ! 1883: \moddef{functions for computing sizes}\endmoddef ! 1884: fun movesize (Direct _) = 1 ! 1885: | movesize (Immed i) = if abs(i)<32768 then 1 else 2 ! 1886: | movesize (Immedlab(ref lab)) = easize(Immed (4*(lab-(get pcptr)))) ! 1887: ! 1888: \endcode ! 1889: \begincode{60} ! 1890: \moddef{cases for sizes to be computed}\endmoddef ! 1891: | MOVE (src,_) => movesize src ! 1892: | LDI_32 _ => 2 ! 1893: | LUI _ => 1 ! 1894: \endcode ! 1895: \begincode{61} ! 1896: \moddef{cases of instructions to be emitted}\endmoddef ! 1897: | MOVE stuff => domove stuff ! 1898: | LDI_32 (immedconst, Reg dest) => ! 1899: let val (hi,lo) = split immedconst ! 1900: in gen1(emit(lui(dest,hi));emit(addi(dest,dest,lo))) ! 1901: end ! 1902: | LUI (Reg dest,immed16) => gen1(emit(lui(dest,immed16))) ! 1903: ! 1904: \endcode ! 1905: \begindocs{62} ! 1906: ! 1907: Now that we've done arithmetic, we can see how to do control flow without ! 1908: too much trouble. ! 1909: \code{}SLT\edoc{} can be treated just like an arithmetic operator. ! 1910: \code{}BEQ\edoc{} is simple if the address to which we branch is close enough. ! 1911: Otherwise we use the following sequence for \code{}BEQ(Reg op1, Reg op2, ref dest)\edoc{}: ! 1912: \verbatim ! 1913: bne op1,op2,L ! 1914: ADD (Reg pcreg, Immed (4*(dest-pcptr)), Reg tempreg) ! 1915: jr tempreg ! 1916: L: ... ! 1917: \endverbatim ! 1918: Notice we don't have to put a \code{}NOP\edoc{} in the delay slot of the \code{}bne\edoc{}. ! 1919: We don't need one after the jump unless we needed one after the ! 1920: original \code{}BEQ\edoc{}, in which case one will be there. ! 1921: If the branch is taken, we're doing as well as we can. ! 1922: If the branch is not taken, we will have executed an \code{}add\edoc{} or \code{}lui\edoc{} in the ! 1923: delay slot of the \code{}bne\edoc{}, but the results just get thrown away. ! 1924: \enddocs ! 1925: \begincode{63} ! 1926: \moddef{cases for sizes to be computed}\endmoddef ! 1927: | SLT(_, ea, _) => easize ea ! 1928: | BEQ(_,_,_,ref dest) => ! 1929: if abs((pos+1)-dest) < 32768 then 1 (* single instruction *) ! 1930: else 2+easize (Immed (4*(dest-(get pcptr)))) ! 1931: | JUMP _ => 1 ! 1932: | SLT_D _ => 1 ! 1933: | SEQ_D _ => 1 ! 1934: | BCOP1(_,ref dest) => ! 1935: if abs((pos+1)-dest) < 32768 then 1 (* single instruction *) ! 1936: else 2+easize (Immed (4*(dest-(get pcptr)))) ! 1937: | NOP => 1 ! 1938: \endcode ! 1939: \begindocs{64} ! 1940: The implementation is as described, except we use a ! 1941: non-standard \code{}nop\edoc{}. ! 1942: There are many Mips instructions that have no effect, and the standard ! 1943: one is the word with all zeroes (\code{}sll 0,0,0\edoc{}). ! 1944: We use \code{}add\edoc{}, adding 0 to 0 and store the result in 0, because it ! 1945: will be easy to distinguish from a data word that happens to be zero. ! 1946: \enddocs ! 1947: \begincode{65} ! 1948: \moddef{cases of instructions to be emitted}\endmoddef ! 1949: | SLT stuff => arith (SLT,slt,slti) stuff ! 1950: | BEQ(b, Reg op1, Reg op2, ref dest) => ! 1951: if size = 1 then ! 1952: gen1(emit((if b then beq else bne)(op1,op2,dest-(pos+1)))) ! 1953: else gen(pos,pcptr, ! 1954: (ref 1, BEQ(not b, Reg op1, Reg op2, ref(pos+size))) ! 1955: ::(ref (size-2), ! 1956: ADD(Reg pcreg, Immed(4*(dest-(get pcptr))), Reg tempreg)) ! 1957: ::(ref 1, JUMP(Reg tempreg)) ! 1958: ::rest) ! 1959: | JUMP(Reg dest) => gen1(emit(jr(dest))) ! 1960: | SLT_D (Reg op1, Reg op2) => ! 1961: gen1(emit(c_lt(D_fmt,op1,op2))) ! 1962: | SEQ_D (Reg op1, Reg op2) => ! 1963: gen1(emit(c_seq(D_fmt,op1,op2))) ! 1964: | BCOP1(b, ref dest) => ! 1965: let fun bc1f offset = cop1(8,0,offset) ! 1966: fun bc1t offset = cop1(8,1,offset) ! 1967: in if size = 1 then ! 1968: gen1(emit((if b then bc1t else bc1f)(dest-(pos+1)))) ! 1969: else gen(pos,pcptr, ! 1970: (ref 1, BCOP1(not b, ref(pos+size))) ! 1971: ::(ref (size-2), ! 1972: ADD(Reg pcreg, Immed(4*(dest-(get pcptr))), Reg tempreg)) ! 1973: ::(ref 1, JUMP(Reg tempreg)) ! 1974: ::rest) ! 1975: end ! 1976: | NOP => gen1(emit(add(0,0,0))) (* one of the many MIPS no-ops *) ! 1977: \endcode ! 1978: \begindocs{66} ! 1979: ! 1980: Our next problem is to tackle load and store. ! 1981: The major difficulty is if the offset is too large to fit in ! 1982: sixteen bits; if so, we have to create a new base register. ! 1983: If we have \code{}Immedlab\edoc{}, we do it as an offset from \code{}pcreg\edoc{}. ! 1984: \enddocs ! 1985: \begincode{67} ! 1986: \moddef{functions for emitting instructions}\endmoddef ! 1987: fun memop(rform,Reg dest, Direct (Reg base), offset) = ! 1988: (case size ! 1989: of 1 => gen1(emit(rform(dest,offset,base))) ! 1990: | 3 => let val (hi,lo) = split offset ! 1991: in gen1(emit(lui(tempreg,hi)); (* tempreg = hi \LL{} 16 *) ! 1992: emit(add(tempreg,base,tempreg));(* tempreg += base *) ! 1993: emit(rform(dest,lo,tempreg)) (* load dest,lo(tempreg) *) ! 1994: ) ! 1995: end ! 1996: | _ => gen1(ErrorMsg.impossible "bad size in memop Direct in mipscoder") ! 1997: ) ! 1998: | memop(rform,Reg dest, Immed address, offset) = ! 1999: (case size ! 2000: of 1 => gen1(emit(rform(dest,offset+address,0))) ! 2001: | 2 => let val (hi,lo) = split (offset+address) ! 2002: in gen1(emit(lui(tempreg,hi)); ! 2003: emit(rform(dest,lo,tempreg)) ! 2004: ) ! 2005: end ! 2006: | _ => gen1(ErrorMsg.impossible "bad size in memop Immed in mipscoder") ! 2007: ) ! 2008: | memop(rform,Reg dest, Immedlab (ref lab), offset) = ! 2009: memop(rform, Reg dest, Direct (Reg pcreg), offset+4*(lab - get pcptr)) ! 2010: \endcode ! 2011: \begindocs{68} ! 2012: The actual registers don't matter for computing sizes, and in fact ! 2013: the value of \code{}pcreg\edoc{} is not visible here, so we use an arbitrary ! 2014: register (\code{}Reg 0\edoc{}) to compute the size. ! 2015: \enddocs ! 2016: \begincode{69} ! 2017: \moddef{functions for computing sizes}\endmoddef ! 2018: fun adrsize(_, Reg _, Direct _, offset) = ! 2019: if abs(offset)<32768 then 1 else 3 ! 2020: | adrsize(_, Reg _, Immed address, offset) = ! 2021: if abs(address+offset) < 32768 then 1 else 2 ! 2022: | adrsize(x, Reg dest, Immedlab (ref lab), offset) = ! 2023: adrsize(x, Reg dest, Direct (Reg 0 (* pcreg in code *) ), ! 2024: offset+4*(lab-(get pcptr))) ! 2025: \endcode ! 2026: \begincode{70} ! 2027: \moddef{cases for sizes to be computed}\endmoddef ! 2028: | LOAD x => adrsize x ! 2029: | STORE x => adrsize x ! 2030: \endcode ! 2031: \begincode{71} ! 2032: \moddef{cases of instructions to be emitted}\endmoddef ! 2033: | LOAD (Byte,dest,address,offset) => memop(lbu,dest,address,offset) ! 2034: | LOAD (Word,dest,address,offset) => memop(lw,dest,address,offset) ! 2035: | LOAD (Floating,dest,address,offset) => memop(lwc1,dest,address,offset) ! 2036: | STORE (Byte,dest,address,offset) => memop(sb,dest,address,offset) ! 2037: | STORE (Word,dest,address,offset) => memop(sw,dest,address,offset) ! 2038: | STORE (Floating,dest,address,offset) => memop(swc1,dest,address,offset) ! 2039: \endcode ! 2040: \begindocs{72} ! 2041: ! 2042: For the shift instructions, only register and immediate operands ! 2043: make sense. ! 2044: Immediate operands make sense if and only if they are representable ! 2045: in five bits. ! 2046: If everything is right, these are single instructions. ! 2047: \enddocs ! 2048: \begincode{73} ! 2049: \moddef{cases for sizes to be computed}\endmoddef ! 2050: | SLL _ => 1 ! 2051: | SRA _ => 1 ! 2052: \endcode ! 2053: \begincode{74} ! 2054: \moddef{cases of instructions to be emitted}\endmoddef ! 2055: | SLL (Immed shamt, Reg op1, Reg result) => gen1( ! 2056: if (shamt >= 0 andalso shamt < 32) then emit(sll(result,op1,shamt)) ! 2057: else ErrorMsg.impossible ("bad sll shamt " ! 2058: ^ (Integer.makestring shamt) ^ " in mipscoder")) ! 2059: | SLL (Direct(Reg shamt), Reg op1, Reg result) => ! 2060: gen1(emit(sllv(result,op1,shamt))) ! 2061: | SLL (Immedlab _,_,_) => ErrorMsg.impossible "sll shamt is Immedlab in mipscoder" ! 2062: | SRA (Immed shamt, Reg op1, Reg result) => gen1( ! 2063: if (shamt >= 0 andalso shamt < 32) then emit(sra(result,op1,shamt)) ! 2064: else ErrorMsg.impossible ("bad sra shamt " ! 2065: ^ (Integer.makestring shamt) ^ " in mipscoder")) ! 2066: | SRA (Direct(Reg shamt), Reg op1, Reg result) => ! 2067: gen1(emit(srav(result,op1,shamt))) ! 2068: | SRA (Immedlab _,_,_) => ErrorMsg.impossible "sra shamt is Immedlab in mipscoder" ! 2069: \endcode ! 2070: \begindocs{75} ! 2071: ! 2072: Finally, comments are ignored, and marks (backpointers) are written into the ! 2073: instruction stream. ! 2074: ! 2075: Comments are used by the front end to give diagnostics. ! 2076: In the bad old days we would have had two different \code{}MIPSCODER\edoc{}s, one ! 2077: which generated machine code (and ignored comments), and one which ! 2078: wrote out assembly code (and copied comments). ! 2079: Today we have just one, which means the rerouting of comments takes place ! 2080: at a much higher level. Look in \code{}cps/mipsglue.nw\edoc{}. ! 2081: \enddocs ! 2082: \begincode{76} ! 2083: \moddef{cases for sizes to be computed}\endmoddef ! 2084: | COMMENT _ => 0 ! 2085: | MARK => 1 (* backpointer takes one word *) ! 2086: \endcode ! 2087: \begindocs{77} ! 2088: Just for the record, here's the description of what a mark (backpointer) ! 2089: is. ! 2090: ``Take the byte address at which the mark resides and add 4, giving ! 2091: the byte address of the object following the mark. ! 2092: (That object is the marked object.) ! 2093: Subtract the byte address of the initial word that marks the ! 2094: start of this instruction stream. ! 2095: Now divide by 4, giving the distance in words between the ! 2096: beginning of the block and the marked object. ! 2097: Take that quantity and shift it left by multiplying by \code{}power_tags\edoc{}, ! 2098: and indicate the result is a mark by adding the tag bits \code{}tag_backptr\edoc{} ! 2099: into the low order part.'' ! 2100: \code{}pos+1\edoc{} is exactly the required distance in words. ! 2101: \enddocs ! 2102: \begincode{78} ! 2103: \moddef{cases of instructions to be emitted}\endmoddef ! 2104: | COMMENT _ => gen1() ! 2105: | MARK => gen1( ! 2106: let open System.Tags ! 2107: in emitlong((pos+1) * power_tags + tag_backptr) ! 2108: end) ! 2109: \endcode ! 2110: \begindocs{79} ! 2111: ! 2112: \enddocs ! 2113: \begindocs{80} ! 2114: \subsection{Optimization} ! 2115: The first step towards optimization is to take statistics. ! 2116: We will count: \code{}instrs\edoc{}, Mips words, \code{}NOP\edoc{}s in load and branch delays, ! 2117: and \code{}bltzal\edoc{}s. ! 2118: In the current implementation the \code{}bltzal\edoc{}s are implicit, so there ! 2119: is no way to count them or optimize them. ! 2120: \enddocs ! 2121: \begincode{81} ! 2122: \moddef{statistics}\endmoddef ! 2123: fun printstats stream ! 2124: \{inst : int, code : int, data : int, ! 2125: load : int, branch : int, compare : int, size : int\} = ! 2126: let val print = output stream ! 2127: val nop = load+branch+compare ! 2128: val bltzal = size - (code + data) ! 2129: val code = code + bltzal ! 2130: \LA{}definition of \code{}sprintf\edoc{}\RA{} ! 2131: fun P x = substring(makestring(100.0 * x),0,4) (* percent *) ! 2132: fun printf f d = print (sprintf f d) ! 2133: in printf ["Counted "," instrs in "," words (", ! 2134: " code, "," data)\\n" ^ ! 2135: "Used "," NOPs ("," load, "," branch,"," compare) and "," bltzals\\n" ^ ! 2136: "","% of code words were NOPs; ","% were bltzals\\n" ^ ! 2137: "","% of all words were code; ","% of all words were NOPs\\n"] ! 2138: [I inst, I size, I code, I data, ! 2139: I nop, I load, I branch, I compare, I bltzal, ! 2140: P (real nop / real code), P (real bltzal / real code), ! 2141: P (real code / real size), P (real nop / real size)] ! 2142: handle Overflow => print "[Overflow in computing Mips stats]\\n" ! 2143: | Real s => print ("[FPE ("^s^") in computing Mips stats]\\n") ! 2144: end ! 2145: ! 2146: \endcode ! 2147: \begincode{82} ! 2148: \moddef{statistics}\endmoddef ! 2149: \LA{}definition of \code{}iscode\edoc{}\RA{} ! 2150: fun addstats (counts as \{inst,code,data,load,branch,compare\}) = ! 2151: fn nil => counts ! 2152: | (sizeref,first)::(_,NOP)::rest => addstats ! 2153: \{inst=inst+2, code=code+(!sizeref)+1, data=data, ! 2154: load=load+ (case first of LOAD _ => 1 | _ => 0), ! 2155: branch=branch +(case first of BEQ _ => 1 | JUMP _ => 1 ! 2156: | BCOP1 _ => 1 | _ => 0), ! 2157: compare=compare+(case first of SLT_D _ => 1 | SEQ_D _ => 1 ! 2158: | _ => 0) ! 2159: \} rest ! 2160: | (sizeref,first)::rest => addstats ! 2161: \{inst=inst+1, ! 2162: code = code + if iscode(first) then !sizeref else 0, ! 2163: data = data + if not (iscode first) then !sizeref else 0, ! 2164: load=load, ! 2165: branch=branch, ! 2166: compare=compare ! 2167: \} rest ! 2168: ! 2169: ! 2170: fun codestats outfile = ! 2171: let val \{size,stream=instrs\} = prepare (!kept) ! 2172: val zero = \{inst=0, code=0, data=0, load=0, branch=0, compare=0\} ! 2173: val counts as \{inst,code,data,load,branch,compare\} = ! 2174: addstats zero instrs ! 2175: in printstats outfile ! 2176: \{inst=inst,code=code,data=data, ! 2177: load=load,branch=branch,compare=compare,size=size\} ! 2178: end ! 2179: ! 2180: \endcode ! 2181: \begincode{83} ! 2182: \moddef{definition of \code{}iscode\edoc{}}\endmoddef ! 2183: val iscode = fn ! 2184: STRINGCONST _ => false ! 2185: | REALCONST _ => false ! 2186: | EMITLONG _ => false ! 2187: | DEFINE _ => false ! 2188: | EMITLAB _ => false ! 2189: ! 2190: | SLT _ => true ! 2191: | BEQ _ => true ! 2192: | JUMP _ => true ! 2193: | NOP => true ! 2194: | SLT_D _ => true ! 2195: | SEQ_D _ => true ! 2196: | BCOP1 _ => true ! 2197: ! 2198: | ADD _ => true ! 2199: | AND _ => true ! 2200: | OR _ => true ! 2201: | XOR _ => true ! 2202: | SUB _ => true ! 2203: | MULDIV _ => true ! 2204: | MFLO _ => true ! 2205: | MFHI _ => true ! 2206: ! 2207: | NEG_D _ => true ! 2208: | MUL_D _ => true ! 2209: | DIV_D _ => true ! 2210: | ADD_D _ => true ! 2211: | SUB_D _ => true ! 2212: ! 2213: | MOVE _ => true ! 2214: | LDI_32 _ => true ! 2215: | LUI _ => true ! 2216: ! 2217: | LOAD _ => true ! 2218: | STORE _ => true ! 2219: ! 2220: | SLL _ => true ! 2221: | SRA _ => true ! 2222: ! 2223: | COMMENT _ => false ! 2224: | MARK => false ! 2225: ! 2226: \endcode ! 2227: \begincode{84} ! 2228: \moddef{definition of \code{}sprintf\edoc{}}\endmoddef ! 2229: val I = Integer.makestring ! 2230: val R = Real.makestring ! 2231: exception Printf ! 2232: fun sprintf format values = ! 2233: let fun merge([x],nil) = [x] ! 2234: | merge(nil,nil) = nil ! 2235: | merge(x::y,z::w) = x::z:: merge(y,w) ! 2236: | merge _ = raise Printf ! 2237: in implode(merge(format,values)) ! 2238: end ! 2239: ! 2240: \endcode ! 2241: \begindocs{85} ! 2242: ! 2243: At the moment these functions are meaningless junk. ! 2244: \enddocs ! 2245: \begincode{86} ! 2246: \moddef{functions that remove pipeline bubbles}\endmoddef ! 2247: val rec squeeze = ! 2248: ! 2249: fn (x as LOAD(_,Reg d, m, i))::NOP::instr::rest => ! 2250: if use(instr,d) then ?? ! 2251: else squeeze(x::instr::rest) ! 2252: | (x as STORE _)::(y as LOAD _)::rest => ! 2253: x :: squeeze(y::rest) ! 2254: | instr::(x as LOAD(_,Reg d, Direct(Reg s), i))::NOP::rest => ! 2255: if use(instr, d) orelse gen(instr, s) then ?? ! 2256: else squeeze(x::instr::rest) ! 2257: | instr::(x as LOAD(_,Reg d, _, i))::NOP::rest => ! 2258: if use(instr,d) then ?? ! 2259: else squeeze(x::instr::rest) ! 2260: | (x as MFLO _):: (y as MULDIV _) :: rest => ! 2261: x :: squeeze (y::rest) ! 2262: | (x as MFLO(Reg d))::instr::rest => ! 2263: if (use(instr,d) orelse gen(instr,d) then ?? ! 2264: else squeeze(instr::x::rest) ! 2265: | instr :: (x as MULDIV(Reg a, Reg b)) :: rest => ! 2266: if gen(instr,a) orelse gen(instr,b) then ?? ! 2267: else squeeze(x::instr::rest) ! 2268: ! 2269: val rec final = ! 2270: fn ! 2271: | instr::(x as LOAD(_,Reg d, Direct(Reg s), i))::NOP::rest => ! 2272: if gen(instr, s) then instr::final(x::NOP::rest) ! 2273: else x::instr::(final rest) ! 2274: | instr :: (x as JUMP _) :: NOP :: rest => ! 2275: x :: instr :: final rest ! 2276: | instr :: (x as BEQ(_,Reg a, Reg b, _)) :: NOP :: rest => ! 2277: if gen(instr,a) orelse gen(instr,b) then instr::x::NOP::(final rest) ! 2278: else x::instr::(final rest) ! 2279: ! 2280: ! 2281: \endcode ! 2282: \filename{opcodes.nw} ! 2283: \begindocs{0} ! 2284: \chapter{Handling the MIPS opcodes} ! 2285: \section{Introduction} ! 2286: ! 2287: This file generates the code necessary to handle MIPS instructions ! 2288: in a natural, mnemonic way from within ML. ! 2289: All MIPS instructions occupy 32 bits, and since ML has no simple ! 2290: 32~bit data type, we use pairs of integerss to represent MIPS instructions. ! 2291: A pair \code{}(hi,lo)\edoc{} of 16-bit integers holds the most and least significant ! 2292: halfwords of the MIPS word. ! 2293: ML integers are 31 bits, so this is more than adequate. ! 2294: ! 2295: The biggest hassle in converting between these integer pairs and more ! 2296: mnemonic representations is that it is too easy to make mistakes ! 2297: (especially typographical errors) in writing the code. ! 2298: For that reason, I have added an extra level of indirection to the ! 2299: whole business by putting all of the instruction descriptions in ! 2300: tables. ! 2301: These tables are read by an awk script, which writes two ML files: ! 2302: {\tt opcodes.sml} and {\tt mipsdecode.sml}. ! 2303: The {\tt opcodes.sml} file contains the code needed to convert from ! 2304: a mnemonic like \code{}add(3,4,9)\edoc{} (add the contents of register~3 to ! 2305: the contents of register~4, placing the result in register~9) to ! 2306: the integer pair representation of the actual bits in that add instruction ! 2307: (in this case \code{}(137,6176)\edoc{}). ! 2308: The {\tt mipsdecode.sml} file contains a \code{}decode\edoc{} function that converts ! 2309: from the integer pair representation of instructions to a string ! 2310: representation. ! 2311: The string representation is a little hokey at the moment (that is, ! 2312: it's different from the one used in the MIPS book), but it represents ! 2313: a nice compromise between being readable and easy to generate. ! 2314: ! 2315: I have contemplating generating a third file to test the whole ! 2316: business. ! 2317: The idea would be to have a function that would write out (to files) ! 2318: two ! 2319: parallel representations of the same instruction stream (presumably ! 2320: one copy of each known instruction). ! 2321: One representation would be the binary one understood by the MIPS. ! 2322: The other representation would be a string representation. ! 2323: We could then use a tool like {\tt gdb} or {\tt adb} to print out ! 2324: the binary as an instruction sequence (i.e. convert back to ! 2325: a second string representation) and compare the string representations ! 2326: to see if they make sense. ! 2327: ! 2328: \paragraph{Possible bugs} ! 2329: This code should be gone over with care to make sure that negative ! 2330: operands (e.g. in \code{}offset\edoc{}) won't break the code. ! 2331: ! 2332: ! 2333: \enddocs ! 2334: \begindocs{1} ! 2335: ! 2336: We need a special line in the Makefile to handle this file, since ! 2337: it writes both an awk program and that program's input. The input ! 2338: is in module {\tt \LL{}opcodes table\GG{}} so the line is ! 2339: $$\hbox{\code{} $(NOTANGLE) '-Ropcodes table' opcodes.ow > opcodes\edoc{}}$$ ! 2340: The input is nothing but a sequence of tables, each labelled, and ! 2341: processed one after anothing according to the label. ! 2342: The label is always a single word on a line by itself. ! 2343: Tables end with blank lines. ! 2344: \enddocs ! 2345: \begindocs{2} ! 2346: The opcode-to-pair code is written to the standard output, in ! 2347: \code{}structure Opcodes\edoc{}. ! 2348: The pair-to-string code is written to \code{}"mipsdecode.sml"\edoc{}, in ! 2349: \code{}structure MipsDecode\edoc{}. ! 2350: ! 2351: We begin by defining and and shift functions. ! 2352: We make pessimistic assumptions about shifting, trying always to ! 2353: keep the arguments between 0 and 31 inclusive. ! 2354: \enddocs ! 2355: \begincode{3} ! 2356: \moddef{BEGIN}\endmoddef ! 2357: print "structure Opcodes = struct" ! 2358: print "val andb = Bits.andb" ! 2359: print "fun lshift(op1,amt) = " ! 2360: print " if amt<0 then Bits.rshift(op1,0-amt)" ! 2361: print " else Bits.lshift(op1,amt)" ! 2362: print "nonfix sub" # bug fixes; want \code{}sub\edoc{} to be a MIPS opcode ! 2363: print "nonfix div" # bug fixes; want \code{}div\edoc{} to be a MIPS opcode ! 2364: ! 2365: decode = "mipsdecode.sml"; ! 2366: print "structure MipsDecode = struct" > decode ! 2367: print "val andb = Bits.andb" > decode ! 2368: print "fun rshift(op1,amt) = " > decode ! 2369: print " if amt<0 then Bits.lshift(op1,0-amt)" > decode ! 2370: print " else Bits.rshift(op1,amt)" > decode ! 2371: \endcode ! 2372: \begincode{4} ! 2373: \moddef{END}\endmoddef ! 2374: \LA{}write out the definitions of the decoding functions\RA{} ! 2375: print "end (* Opcodes *)" ! 2376: print "end (* Decode *)" > decode ! 2377: \endcode ! 2378: \begindocs{5} ! 2379: The sections BEGIN and END are drawn from ! 2380: our universal model of an awk program: ! 2381: \enddocs ! 2382: \begincode{6} ! 2383: \moddef{*}\endmoddef ! 2384: BEGIN \{ ! 2385: \LA{}BEGIN\RA{} ! 2386: \} ! 2387: \LA{}functions\RA{} ! 2388: \LA{}statements\RA{} ! 2389: END \{ ! 2390: \LA{}END\RA{} ! 2391: \} ! 2392: \endcode ! 2393: \begindocs{7} ! 2394: \section{The opcode tables} ! 2395: The numeric codes for all the MIPS opcodes are described in three ! 2396: tables in the MIPS book on page~A-87. ! 2397: Normal opcodes are six bits, and appear in the \code{}opcode\edoc{} field of the ! 2398: instruction. ! 2399: Two opcodes \code{}special\edoc{} and \code{}bcond\edoc{} stand for several instructions. ! 2400: These instructions are decoded by checking the bit-pattern in the ! 2401: \code{}funct\edoc{} and \code{}cond\edoc{} fields of the instructions, respectively. ! 2402: ! 2403: The tables show which opcodes correspond to which bit-patterns. ! 2404: For example, the \code{}slti\edoc{} corresponds to an \code{}opcode\edoc{} value of octal~12. ! 2405: The table headed \code{}opcode\edoc{} gives the mnemonics for all six-bit patterns ! 2406: in the \code{}opcode\edoc{} field. ! 2407: The \code{}special\edoc{} table shows patterns for the \code{}funct\edoc{} field, used with ! 2408: the \code{}special\edoc{} opcode. ! 2409: The \code{}bcond\edoc{} table shows five-bit patterns for the \code{}cond\edoc{} field, ! 2410: used with the \code{}bcond\edoc{} opcode. ! 2411: In all tables, stars (\code{}*\edoc{}) stand for unused fields. ! 2412: ! 2413: Each table is terminated with a blank line. ! 2414: \enddocs ! 2415: \begincode{8} ! 2416: \moddef{opcodes table}\endmoddef ! 2417: opcode ! 2418: special bcond j jal beq bne blez bgtz ! 2419: addi addiu slti sltiu andi ori xori lui ! 2420: cop0 cop1 cop2 cop3 * * * * ! 2421: * * * * * * * * ! 2422: lb lh lwl lw lbu lhu lwr * ! 2423: sb sh swl sw * * swr * ! 2424: lwc0 lwc1 lwc2 lwc3 * * * * ! 2425: swc0 swc1 swc2 swc3 * * * * ! 2426: ! 2427: special ! 2428: sll * srl sra sllv * srlv srav ! 2429: jr jalr * * syscall break * * ! 2430: mfhi mthi mflo mtlo * * * * ! 2431: mult multu div divu * * * * ! 2432: add addu sub subu and' or xor nor ! 2433: * * slt sltu * * * * ! 2434: * * * * * * * * ! 2435: * * * * * * * * ! 2436: ! 2437: bcond ! 2438: bltz bgez * * * * * * ! 2439: * * * * * * * * ! 2440: bltzal bgezal * * * * * * ! 2441: * * * * * * * * ! 2442: ! 2443: ! 2444: \endcode ! 2445: \begindocs{9} ! 2446: The instructions codes for Coprocessor 1 (floating point) ! 2447: are takin from page B-28 of the Mips book. ! 2448: \enddocs ! 2449: \begincode{10} ! 2450: \moddef{opcodes table}\endmoddef ! 2451: cop1 ! 2452: add_fmt sub_fmt mul_fmt div_fmt * abs_fmt mov_fmt neg_fmt ! 2453: * * * * * * * * ! 2454: * * * * * * * * ! 2455: * * * * * * * * ! 2456: cvt_s cvt_d * * cvt_w * * * ! 2457: * * * * * * * * ! 2458: c_f c_un c_eq c_ueq c_olt c_ult c_ole c_ule ! 2459: c_sf c_ngle c_seq c_ngl c_lt c_nge c_le c_ngt ! 2460: ! 2461: \endcode ! 2462: \begindocs{11} ! 2463: ! 2464: Now we have to deal with reading these tables, and extracting the ! 2465: information stored therein. ! 2466: First of all, for each mnemonic \code{}$i\edoc{} we store the corresponding bit ! 2467: pattern (as an integer, \code{}code\edoc{}) in the array \code{}numberof[$i] \edoc{}. ! 2468: Then, we store the type of the mnemonic (ordinary \code{}OPCODE\edoc{}, ! 2469: \code{}SPECIAL\edoc{}, \code{}BCOND\edoc{}, of \code{}COP1\edoc{}) in the array \code{}typeof[$i] \edoc{}. ! 2470: Finally, we store inverse (a map from type and bit pattern to mnemonic) ! 2471: in the \code{}opcode\edoc{} array. ! 2472: \enddocs ! 2473: \begincode{12} ! 2474: \moddef{store opcode information}\endmoddef ! 2475: if ($i != "*") \{ ! 2476: numberof[$i] = code ! 2477: typeof[$i] = type ! 2478: opcode[type,code] = $i ! 2479: \} else \{ ! 2480: opcode[type,code] = "reserved" ! 2481: \} ! 2482: \endcode ! 2483: \begindocs{13} ! 2484: The types are just constants set at the beginning. ! 2485: \enddocs ! 2486: \begincode{14} ! 2487: \moddef{BEGIN}\endmoddef ! 2488: OPCODE = 1 ; SPECIAL = 2 ; BCOND = 3 ; COP1 = 4 ! 2489: \endcode ! 2490: \begindocs{15} ! 2491: We determine the type by scanning the header word that precedes ! 2492: each table. ! 2493: Once we see the appropriate table header, we set one of \code{}opcodes\edoc{}, ! 2494: \code{}specials\edoc{}, and \code{}bconds\edoc{}, so that determining the type is easy: ! 2495: \enddocs ! 2496: \begincode{16} ! 2497: \moddef{set \code{}type\edoc{}}\endmoddef ! 2498: type = OPCODE * opcodes + SPECIAL * specials + BCOND * bconds + COP1 * cop1s ! 2499: \endcode ! 2500: \begindocs{17} ! 2501: Seeing the right table header causes us to set the right variable. ! 2502: We also remember the line number, because we use the positions of later ! 2503: lines to help extract the bit patterns from the table. ! 2504: \enddocs ! 2505: \begincode{18} ! 2506: \moddef{statements}\endmoddef ! 2507: NF == 1 && $1 == "opcode" \{ ! 2508: startline = NR ! 2509: opcodes = 1 ! 2510: next ! 2511: \} ! 2512: NF == 1 && $1 == "special" \{ ! 2513: startline = NR ! 2514: specials = 1 ! 2515: next ! 2516: \} ! 2517: NF == 1 && $1 == "bcond" \{ ! 2518: startline = NR ! 2519: bconds = 1 ! 2520: next ! 2521: \} ! 2522: NF == 1 && $1 == "cop1" \{ ! 2523: startline = NR ! 2524: cop1s = 1 ! 2525: next ! 2526: \} ! 2527: \endcode ! 2528: \begindocs{19} ! 2529: Any time we see a blank line, that ends the appropriate table. ! 2530: \enddocs ! 2531: \begincode{20} ! 2532: \moddef{statements}\endmoddef ! 2533: NF == 0 \{opcodes = 0; specials = 0; bconds = 0; cop1s = 0 ! 2534: \LA{}blank line resets\RA{} ! 2535: \} ! 2536: \endcode ! 2537: \begindocs{21} ! 2538: Here is the code that actually extracts the bit patterns from ! 2539: the opcode tables. ! 2540: The code is the same for each of the three tables. ! 2541: ! 2542: The \code{}insist_fields(8)\edoc{} issues an error message and returns false (0) ! 2543: unless there are exactly 8 fields on the input line. ! 2544: \enddocs ! 2545: \begincode{22} ! 2546: \moddef{statements}\endmoddef ! 2547: opcodes || specials || bconds || cop1s \{ ! 2548: if (!insist_fields(8)) next ! 2549: \LA{}set \code{}type\edoc{}\RA{} ! 2550: major = NR - startline - 1 # major octal digit from row ! 2551: for (i=1; i<= NF; i++) \{ ! 2552: minor = i-1 # minor octal digit from column ! 2553: code = minor + 8 * major ! 2554: \LA{}store opcode information\RA{} ! 2555: \} ! 2556: \} ! 2557: \endcode ! 2558: \begindocs{23} ! 2559: \section{The instruction fields} ! 2560: Now that we've dealt with the opcodes, we'll handle other fields of ! 2561: the instruction. ! 2562: This table tells us the position of each field within the word, ! 2563: so that if we know a bit-pattern for each field, we can assemble ! 2564: all the fields into an instruction. ! 2565: ! 2566: Not all fields are used in all instructions. ! 2567: Later we'll have a table that indicates exactly which fields are used in ! 2568: which instructions. ! 2569: For now, we just list the fields and their positions with the ! 2570: understanding that some fields will overlap. ! 2571: ! 2572: The table is taken from the MIPS book, page A-3. ! 2573: The numbers are the numbers of the starting and ending bit positions, ! 2574: where 0 is the least and 31 the most significant bit. ! 2575: The names are exactly those used in the book except \code{}op'\edoc{} has been ! 2576: substituted for \code{}op\edoc{} since \code{}op\edoc{} is a reserved word in ML. ! 2577: ! 2578: If a field is signed, we put a \code{}+\edoc{}~sign as the first character ! 2579: of its name. ! 2580: The sign information is used only in decoding (I think). ! 2581: \enddocs ! 2582: \begincode{24} ! 2583: \moddef{opcodes table}\endmoddef ! 2584: fields ! 2585: op' 26 31 ! 2586: rs 21 25 ! 2587: rt 16 20 ! 2588: +immed 0 15 ! 2589: +offset 0 15 ! 2590: base 21 25 ! 2591: target 0 25 ! 2592: rd 11 15 ! 2593: shamt 6 10 ! 2594: funct 0 5 ! 2595: cond 16 20 ! 2596: \LA{}floating point load/store fields\RA{} ! 2597: \LA{}floating point computation fields\RA{} ! 2598: ! 2599: \endcode ! 2600: \begindocs{25} ! 2601: From page B-5. Most fields are the same as the CPU instruction formats. ! 2602: \enddocs ! 2603: \begincode{26} ! 2604: \moddef{floating point load/store fields}\endmoddef ! 2605: ft 16 20 ! 2606: \endcode ! 2607: \begindocs{27} ! 2608: From page B-6. Many fields are reused from earlier specifications. ! 2609: The computational instructions all have a one bit in position 25. ! 2610: Instead of trying to insert special code to handle that, we cheat on ! 2611: it by making that bit part of the format, and cheating on the format. ! 2612: Thus: ! 2613: \enddocs ! 2614: \begincode{28} ! 2615: \moddef{floating point computation fields}\endmoddef ! 2616: fmt 21 25 ! 2617: fs 11 15 ! 2618: fd 6 10 ! 2619: \endcode ! 2620: \begincode{29} ! 2621: \moddef{write format info}\endmoddef ! 2622: print "val S_fmt = 16+0" ! 2623: print "val D_fmt = 16+1" ! 2624: print "val W_fmt = 16+4" ! 2625: ! 2626: \endcode ! 2627: \begindocs{30} ! 2628: The setup for the fields is similar to that used for the opcodes. ! 2629: \enddocs ! 2630: \begincode{31} ! 2631: \moddef{statements}\endmoddef ! 2632: NF == 1 && $1 == "fields" \{ ! 2633: startline = NR ! 2634: fields = 1 ! 2635: \LA{}write format info\RA{} ! 2636: next ! 2637: \} ! 2638: \endcode ! 2639: \begincode{32} ! 2640: \moddef{blank line resets}\endmoddef ! 2641: fields = 0 ! 2642: \endcode ! 2643: \begincode{33} ! 2644: \moddef{statements}\endmoddef ! 2645: fields \{ ! 2646: if (!insist_fields(3)) next ! 2647: fieldname = $1; low = $2; high = $3 ! 2648: \LA{}look for sign in \code{}fieldname\edoc{} and set \code{}signed\edoc{}\RA{} ! 2649: fieldnames[fieldname]= 1 # rememeber all the field names ! 2650: ! 2651: \LA{}write to standard output a function to convert bit-pattern to pair\RA{} ! 2652: \LA{}write to \code{}decode\edoc{} a function to extract field from pair\RA{} ! 2653: ! 2654: \} ! 2655: \endcode ! 2656: \begincode{34} ! 2657: \moddef{look for sign in \code{}fieldname\edoc{} and set \code{}signed\edoc{}}\endmoddef ! 2658: if (substr(fieldname,1,1)=="+") \{ ! 2659: signed = 1 ! 2660: fieldname = substr(fieldname,2) ! 2661: \} else \{ ! 2662: signed = 0 ! 2663: \} ! 2664: \endcode ! 2665: \begindocs{35} ! 2666: ! 2667: The idea is that for each of these fields, we want to write a function ! 2668: that will take an integer argument and shift it by the right amount. ! 2669: Since we have to represent the 32-bit quantities as pairs of integers, ! 2670: we actually use two functions, one for the high half and one for the low. ! 2671: So, for example, for the \code{}rd\edoc{} field we will produce two function definitions, ! 2672: \code{}rdHI\edoc{} and \code{}rdLO\edoc{}. ! 2673: ! 2674: The awk function \code{}function_definition\edoc{} is used to compute ML function ! 2675: definitions. ! 2676: It takes as arguments the name of the function and the number of arguments ! 2677: to that function. ! 2678: The arguments are numbered \code{}A1\edoc{}, \code{}A2\edoc{}, et cetera. ! 2679: ! 2680: The functions themselves are all tedious combinations of ands and shifts. ! 2681: At one time I had convinced myself that this worked. ! 2682: \enddocs ! 2683: \begincode{36} ! 2684: \moddef{write to standard output a function to convert bit-pattern to pair}\endmoddef ! 2685: if (low >= 16) \{ ! 2686: printf "%s", function_definition(fieldname "LO",1); print "0" ! 2687: \} else \{ ! 2688: printf "%s", function_definition(fieldname "LO",1) ! 2689: printf "andb(lshift(A1,%d),65535)\\n", low ! 2690: \} ! 2691: if (high < 16) \{ ! 2692: printf "%s", function_definition(fieldname "HI",1); print "0" ! 2693: \} else \{ ! 2694: printf "%s", function_definition(fieldname "HI",1) ! 2695: printf "lshift(A1,%s)\\n", mlnumber(low - 16) ! 2696: \} ! 2697: \endcode ! 2698: \begindocs{37} ! 2699: The inverse operation is ! 2700: to extract a bit pattern from a pair. ! 2701: We'll want that if we ever care to decode instructions. ! 2702: This time, the function to extract e.g.\ field \code{}rd\edoc{} from a pair ! 2703: is the function \code{}THErd\edoc{} applied to that pair. ! 2704: ! 2705: The functions work first by extracting from the low part, then ! 2706: from the high part, and adding everything together. ! 2707: If the field is signed, we make the value negative if it is too high. ! 2708: \enddocs ! 2709: \begincode{38} ! 2710: \moddef{write to \code{}decode\edoc{} a function to extract field from pair}\endmoddef ! 2711: printf "%s", function_definition("THE" fieldname,2) > decode ! 2712: if (signed) printf "let val n = " > decode ! 2713: \LA{}print expression for unsigned value\RA{} ! 2714: if (signed) \{ ! 2715: printf "in if n < %d then n else n - %d\\nend\\n", ! 2716: 2**(high-low), 2**(high-low+1) > decode ! 2717: \} ! 2718: ! 2719: \endcode ! 2720: \begincode{39} ! 2721: \moddef{print expression for unsigned value}\endmoddef ! 2722: if (low >= 16) \{ ! 2723: printf "0" > decode ! 2724: \} else \{ ! 2725: printf "andb(rshift(A2,%d),%d)", low, ! 2726: (2**(min(15,high)-low+1)-1) > decode ! 2727: \} ! 2728: printf " + " > decode ! 2729: if (high < 16) \{ ! 2730: printf "0\\n" > decode ! 2731: \} else \{ ! 2732: printf "rshift(andb(A1,%d),%s)\\n", (2**(high-16+1)-1), ! 2733: mlnumber(low - 16) > decode ! 2734: \} ! 2735: \endcode ! 2736: \begindocs{40} ! 2737: ML uses a strange minus sign (\code{}~\edoc{} instead of \code{}-\edoc{}), ! 2738: so we print numbers that might be negative like this: ! 2739: \enddocs ! 2740: \begincode{41} ! 2741: \moddef{functions}\endmoddef ! 2742: function mlnumber(n, s) \{ ! 2743: if (n<0) s = sprintf("~%d", -n) ! 2744: else s = sprintf("%d", n) ! 2745: return s ! 2746: \} ! 2747: \endcode ! 2748: \begindocs{42} ! 2749: For reasons best known to its designers, awk has no \code{}min\edoc{} function. ! 2750: \enddocs ! 2751: \begincode{43} ! 2752: \moddef{functions}\endmoddef ! 2753: function min(x,y)\{ ! 2754: if (x<y) return x ! 2755: else return y ! 2756: \} ! 2757: \endcode ! 2758: \begindocs{44} ! 2759: \section{The list of instructions and their formats} ! 2760: This is the section that tells which fields are used in what instructions, ! 2761: and in what order the fields appear. ! 2762: The information is from Appendix A ! 2763: of the MIPS book and should be proofread. ! 2764: ! 2765: To cut down on the number of ML functions generated, we can comment out ! 2766: instructions with a \code{}#\edoc{} in the first column. ! 2767: This means that no code will be generated for the instruction, and ! 2768: it won't appear in the \code{}structure Opcodes\edoc{}. ! 2769: \enddocs ! 2770: \begincode{45} ! 2771: \moddef{opcodes table}\endmoddef ! 2772: instructions ! 2773: add rd rs rt ! 2774: addi rt rs immed ! 2775: addiu rt rs immed ! 2776: addu rd rs rt ! 2777: and' rd rs rt ! 2778: andi rt rs immed ! 2779: beq rs rt offset ! 2780: bgez rs offset ! 2781: bgezal rs offset ! 2782: bgtz rs offset ! 2783: blez rs offset ! 2784: bltz rs offset ! 2785: bltzal rs offset ! 2786: bne rs rt offset ! 2787: break ! 2788: div rs rt ! 2789: divu rs rt ! 2790: j target ! 2791: jal target ! 2792: jalr rs rd ! 2793: jr rs ! 2794: lb rt offset base ! 2795: lbu rt offset base ! 2796: lh rt offset base ! 2797: lb rt offset base ! 2798: lhu rt offset base ! 2799: lui rt immed ! 2800: lw rt offset base ! 2801: lwl rt offset base ! 2802: lwr rt offset base ! 2803: mfhi rd ! 2804: mflo rd ! 2805: mthi rs ! 2806: mtlo rs ! 2807: mult rs rt ! 2808: multu rs rt ! 2809: nor rd rs rt ! 2810: or rd rs rt ! 2811: ori rt rs immed ! 2812: sb rt offset base ! 2813: sh rt offset base ! 2814: sll rd rt shamt ! 2815: sllv rd rt rs ! 2816: slt rd rs rt ! 2817: slti rt rs immed ! 2818: sltiu rt rs immed ! 2819: sltu rd rs rt ! 2820: sra rd rt shamt ! 2821: srav rd rt rs ! 2822: srl rd rt shamt ! 2823: srlv rd rt rs ! 2824: sub rd rs rt ! 2825: subu rd rs rt ! 2826: sw rt offset base ! 2827: swl rt offset base ! 2828: swr rt offset base ! 2829: syscall ! 2830: xor rd rs rt ! 2831: xori rt rs immed ! 2832: \LA{}floating point instructions\RA{} ! 2833: ! 2834: ! 2835: \endcode ! 2836: \begindocs{46} ! 2837: We define only those floating point instructions we seem likely to need. ! 2838: To distinguish them as floating point we append an f to their names. ! 2839: \enddocs ! 2840: \begincode{47} ! 2841: \moddef{floating point instructions}\endmoddef ! 2842: add_fmt fmt fd fs ft ! 2843: div_fmt fmt fd fs ft ! 2844: lwc1 ft offset base ! 2845: mul_fmt fmt fd fs ft ! 2846: neg_fmt fmt fd fs ! 2847: sub_fmt fmt fd fs ft ! 2848: swc1 ft offset base ! 2849: c_seq fmt fs ft ! 2850: c_lt fmt fs ft ! 2851: \endcode ! 2852: \begindocs{48} ! 2853: ! 2854: Here is a terrible hack to enable us to construct branch on coprocessor~1 ! 2855: true or false. ! 2856: We will use \code{}fun bc1f offset = cop1(0,offset)\edoc{} and ! 2857: \code{}fun bc1t offset = cop1(1,offset)\edoc{}. ! 2858: \enddocs ! 2859: \begincode{49} ! 2860: \moddef{floating point instructions}\endmoddef ! 2861: cop1 rs rt offset ! 2862: \endcode ! 2863: \begindocs{50} ! 2864: ! 2865: ! 2866: ! 2867: \enddocs ! 2868: \begindocs{51} ! 2869: For each instruction, we define an ML function with the appropriate ! 2870: number of arguments. ! 2871: When that function is given an integer in each argument, ! 2872: it converts the whole thing to one MIPS instruction, represented as an ! 2873: integer pair. ! 2874: ! 2875: The implementation is a bit of a grubby mess. ! 2876: Doing the fields is straightforward enough, but ! 2877: for each mnemonic we have to do something different based ! 2878: on its type, because each type of opcode goes in a different ! 2879: field. ! 2880: Moreover, for mnemonics of type \code{}SPECIAL\edoc{}, \code{}BCOND\edoc{}, and \code{}COP1\edoc{} we ! 2881: have to generate \code{}special\edoc{}, \code{}bcond\edoc{}, and \code{}cop1\edoc{} in the \code{}op'\edoc{} field. ! 2882: Finally, we have to do it all twice; once for the high order ! 2883: halfword and once for the low order halfword. ! 2884: \enddocs ! 2885: \begincode{52} ! 2886: \moddef{compute function that generates this instruction}\endmoddef ! 2887: printf "%s", function_definition(opname, NF-1) ! 2888: printf "(" # open parenthesis for pair ! 2889: for (i=2; i<= NF; i++) \{ ! 2890: if (!($i in fieldnames)) \LA{}bad field name\RA{} ! 2891: printf "%sHI(A%d)+", $i, i-1 ! 2892: \} ! 2893: if (typeof[opname]==OPCODE) \{ ! 2894: printf "op'HI(%d)", numberof[opname] ! 2895: \} else if (typeof[opname]==SPECIAL) \{ ! 2896: printf "op'HI(%d)+", numberof["special"] ! 2897: printf "functHI(%d)", numberof[opname] ! 2898: \} else if (typeof[opname]==BCOND) \{ ! 2899: printf "op'HI(%d)+", numberof["bcond"] ! 2900: printf "condHI(%d)", numberof[opname] ! 2901: \} else if (typeof[opname]==COP1) \{ ! 2902: printf "op'HI(%d)+", numberof["cop1"] ! 2903: printf "functHI(%d)", numberof[opname] ! 2904: \} else \LA{}bad operator name\RA{} ! 2905: printf ", " ! 2906: for (i=2; i<= NF; i++) \{ ! 2907: if (!($i in fieldnames)) \LA{}bad field name\RA{} ! 2908: printf "%sLO(A%d)+", $i, i-1 ! 2909: \} ! 2910: if (typeof[opname]==OPCODE) \{ ! 2911: printf "op'LO(%d)", numberof[opname] ! 2912: \} else if (typeof[opname]==SPECIAL) \{ ! 2913: printf "op'LO(%d)+", numberof["special"] ! 2914: printf "functLO(%d)", numberof[opname] ! 2915: \} else if (typeof[opname]==BCOND) \{ ! 2916: printf "op'LO(%d)+", numberof["bcond"] ! 2917: printf "condLO(%d)", numberof[opname] ! 2918: \} else if (typeof[opname]==COP1) \{ ! 2919: printf "op'LO(%d)+", numberof["cop1"] ! 2920: printf "functLO(%d)", numberof[opname] ! 2921: \} else \LA{}bad operator name\RA{} ! 2922: printf ")\\n" ! 2923: \endcode ! 2924: \begindocs{53} ! 2925: ! 2926: Setup is as before. ! 2927: \enddocs ! 2928: \begincode{54} ! 2929: \moddef{statements}\endmoddef ! 2930: NF == 1 && $1 == "instructions" \{ ! 2931: startline = NR ! 2932: instructions = 1 ! 2933: next ! 2934: \} ! 2935: \endcode ! 2936: \begincode{55} ! 2937: \moddef{blank line resets}\endmoddef ! 2938: instructions= 0 ! 2939: \endcode ! 2940: \begincode{56} ! 2941: \moddef{statements}\endmoddef ! 2942: instructions && $0 !~ /^#/ \{ ! 2943: opname = $1 ! 2944: ! 2945: \LA{}compute string displayed when this instruction is decoded\RA{} ! 2946: ######## gsub("[^a-z']+"," ") ### ill-advised ! 2947: ! 2948: \LA{}compute function that generates this instruction\RA{} ! 2949: \} ! 2950: ! 2951: \endcode ! 2952: \begindocs{57} ! 2953: \paragraph{Decoding instructions} ! 2954: When we've decoded an instruction, we have to display some sort of ! 2955: string representation that tells us what the instruction is. ! 2956: Ideally we should display either just what the assembler expects, ! 2957: or perhaps just what dbx displays when asked about actual instructions ! 2958: in memory images. ! 2959: ! 2960: For now, we just give the mnemonic for the instruction, followed ! 2961: by a description of each field (followed by a newline). ! 2962: The fields are described as name-value pairs. ! 2963: ! 2964: We rely on the fact that for a field e.g.\ \code{}rd\edoc{}, the string ! 2965: representation of the value of that field is in \code{}Srd\edoc{}. ! 2966: \enddocs ! 2967: \begincode{58} ! 2968: \moddef{compute string displayed when this instruction is decoded}\endmoddef ! 2969: temp = "\\"" opname " \\"" ! 2970: for (i=2; i<=NF; i++) \{ ! 2971: temp = sprintf( "%s ^ \\"%s = \\" ^ S%s", temp, $i, $i) ! 2972: if (i<NF) temp = sprintf("%s ^ \\",\\" ", temp) ! 2973: \} ! 2974: displayof[opname]=temp " ^ \\"\\\\n\\"" ! 2975: ! 2976: \endcode ! 2977: \begindocs{59} ! 2978: The implementation of the decoding function is split into several parts. ! 2979: First, we have to be able to extract any field from an instruction. ! 2980: Then, we have to be able to decode four kinds of opcodes: ! 2981: \code{}OPCODE\edoc{}s, \code{}BCOND\edoc{}s, \code{}SPECIAL\edoc{}s, and \code{}COP1\edoc{}s. ! 2982: The main function is the one that does ordinary opcodes. ! 2983: The others are auxiliary. ! 2984: \enddocs ! 2985: \begincode{60} ! 2986: \moddef{write out the definitions of the decoding functions}\endmoddef ! 2987: printf "%s", function_definition("decode",2) > decode ! 2988: print "let" > decode ! 2989: \LA{}write definitions of integer and string representations of each field\RA{} ! 2990: \LA{}write expression that decodes the \code{}funct\edoc{} field for \code{}special\edoc{}s\RA{} ! 2991: \LA{}write expression that decodes the \code{}cond\edoc{} field for \code{}bcond\edoc{}s\RA{} ! 2992: \LA{}write expression that decodes the \code{}funct\edoc{} field for \code{}cop1\edoc{}s\RA{} ! 2993: print "in" > decode ! 2994: \LA{}write \code{}case\edoc{} expression that decodes the \code{}op'\edoc{} field for each instruction\RA{} ! 2995: print "end" > decode ! 2996: \endcode ! 2997: \begindocs{61} ! 2998: We give each field its own name for an integer version, and its name ! 2999: preceded by \code{}S\edoc{} for its string version. ! 3000: These values are all computed just once, from the arguments to the ! 3001: enclosing function (\code{}decode\edoc{}). ! 3002: \enddocs ! 3003: \begincode{62} ! 3004: \moddef{write definitions of integer and string representations of each field}\endmoddef ! 3005: for (f in fieldnames) \{ ! 3006: printf "val %s = THE%s(A1,A2)\\n", f, f > decode ! 3007: printf "val S%s = Integer.makestring %s\\n", f, f > decode ! 3008: \} ! 3009: \endcode ! 3010: \begindocs{63} ! 3011: The next three functions are very much of a piece. ! 3012: They are just enormous \code{}case\edoc{} expressions that match up integers ! 3013: (bit patterns) to strings. ! 3014: The fundamental operation is printing out a decimal value and a string ! 3015: for each opcode: ! 3016: \enddocs ! 3017: \begincode{64} ! 3018: \moddef{if \code{}name\edoc{} is known, display a case for it}\endmoddef ! 3019: if (name != "" && name != "reserved") \{ ! 3020: \LA{}print space or bar (\code{}|\edoc{})\RA{} ! 3021: disp = displayof[name] ! 3022: if (disp=="") disp="\\"" name "(??? unknown format???)\\\\n\\"" ! 3023: printf "%d => %s\\n", code, disp > decode ! 3024: \} ! 3025: \endcode ! 3026: \begindocs{65} ! 3027: Cases must be separated by vertical bars. ! 3028: We do the separation by putting a vertical bar before each case except ! 3029: the first. ! 3030: We use a hack to discover the first; we assume that code~0 is always ! 3031: defined, and so it will always be the first. ! 3032: \enddocs ! 3033: \begincode{66} ! 3034: \moddef{print space or bar (\code{}|\edoc{})}\endmoddef ! 3035: if (code!=0) printf " | " > decode # hack but it works ! 3036: else printf " " > decode ! 3037: \endcode ! 3038: \begincode{67} ! 3039: \moddef{write expression that decodes the \code{}funct\edoc{} field for \code{}special\edoc{}s}\endmoddef ! 3040: print "val do_special =" > decode ! 3041: print "(case funct of" > decode ! 3042: for (code=0; code<256; code++) \{ ! 3043: name = opcode[SPECIAL,code] ! 3044: \LA{}if \code{}name\edoc{} is known, display a case for it\RA{} ! 3045: \} ! 3046: printf " | _ => \\"unknown special\\\\n\\"\\n" > decode ! 3047: print " ) " > decode ! 3048: \endcode ! 3049: \begincode{68} ! 3050: \moddef{write expression that decodes the \code{}cond\edoc{} field for \code{}bcond\edoc{}s}\endmoddef ! 3051: print "val do_bcond =" > decode ! 3052: print "(case cond of" > decode ! 3053: for (code=0; code<256; code++) \{ ! 3054: name = opcode[BCOND,code] ! 3055: \LA{}if \code{}name\edoc{} is known, display a case for it\RA{} ! 3056: \} ! 3057: printf " | _ => \\"unknown bcond\\\\n\\"\\n" > decode ! 3058: print " ) " > decode ! 3059: \endcode ! 3060: \begincode{69} ! 3061: \moddef{write expression that decodes the \code{}funct\edoc{} field for \code{}cop1\edoc{}s}\endmoddef ! 3062: print "val do_cop1 =" > decode ! 3063: print "(case funct of" > decode ! 3064: for (code=0; code<256; code++) \{ ! 3065: name = opcode[COP1,code] ! 3066: \LA{}if \code{}name\edoc{} is known, display a case for it\RA{} ! 3067: \} ! 3068: printf " | _ => \\"unknown cop1\\\\n\\"\\n" > decode ! 3069: print " ) " > decode ! 3070: \endcode ! 3071: \begindocs{70} ! 3072: The major expression is a little more complicated, because it has to ! 3073: check for \code{}special\edoc{}, \code{}bcond\edoc{}, and \code{}cop1\edoc{} and handle those separately. ! 3074: \enddocs ! 3075: \begincode{71} ! 3076: \moddef{write \code{}case\edoc{} expression that decodes the \code{}op'\edoc{} field for each instruction}\endmoddef ! 3077: print "(case op' of" > decode ! 3078: for (code=0; code<256; code++) \{ ! 3079: name = opcode[OPCODE,code] ! 3080: if (name=="special") \{ ! 3081: \LA{}print space or bar (\code{}|\edoc{})\RA{} ! 3082: printf "%d => %s\\n", code, "do_special" > decode ! 3083: \} else if (name=="bcond") \{ ! 3084: \LA{}print space or bar (\code{}|\edoc{})\RA{} ! 3085: printf "%d => %s\\n", code, "do_bcond" > decode ! 3086: \} else if (name=="cop1") \{ ! 3087: \LA{}print space or bar (\code{}|\edoc{})\RA{} ! 3088: printf "%d => %s\\n", code, "do_cop1" > decode ! 3089: \} else \LA{}if \code{}name\edoc{} is known, display a case for it\RA{} ! 3090: \} ! 3091: printf " | _ => \\"unknown opcode\\\\n\\"\\n" > decode ! 3092: print " ) " > decode ! 3093: \endcode ! 3094: \begindocs{72} ! 3095: \section{testing} ! 3096: One day someone will have to modify the instruction handler so that ! 3097: it generates a test invocation of each instruction. ! 3098: Then the results can be handed to something like adb or dbx and we can ! 3099: see whether the system agrees with us about what we're generating. ! 3100: ! 3101: \enddocs ! 3102: \begindocs{73} ! 3103: \section{Defining ML functions} ! 3104: The awk function \code{}function_definition\edoc{} is used to ! 3105: come up with ML function definitions. ! 3106: It takes as arguments the name of the function and the number of arguments ! 3107: to that function, and returns a string containing the initial part of ! 3108: the function definition. ! 3109: Writing an expression following that string will result in a complete ! 3110: ML function. ! 3111: ! 3112: If we ever wanted to define these things as C preprocessor macros instead, ! 3113: we could do it by substituting \code{}macro_definition\edoc{}. ! 3114: I'm not sure it would ever make sense to do so, but I'm leaving the ! 3115: code here anyway. ! 3116: \enddocs ! 3117: \begincode{74} ! 3118: \moddef{functions}\endmoddef ! 3119: function function_definition(name, argc, i, temp) \{ ! 3120: if (argc==0) \{ ! 3121: temp = sprintf("val %s = ", name) ! 3122: \} else \{ ! 3123: temp = sprintf( "fun %s(", name) ! 3124: for (i=1; i< argc; i++) temp = sprintf("%sA%d,", temp,i) ! 3125: temp = sprintf( "%sA%d) = ", temp, argc) ! 3126: \} ! 3127: return temp ! 3128: \} ! 3129: \endcode ! 3130: \begincode{75} ! 3131: \moddef{useless functions}\endmoddef ! 3132: function macro_definition(name, argc, i, temp) \{ ! 3133: if (argc==0) \{ ! 3134: temp = sprintf("#define %s ", name) ! 3135: \} else \{ ! 3136: temp = sprintf( "#define %s(", name) ! 3137: for (i=1; i< argc; i++) temp = sprintf("%sA%d,", temp,i) ! 3138: temp = sprintf( "%sA%d) ", temp, argc) ! 3139: \} ! 3140: return temp ! 3141: \} ! 3142: \endcode ! 3143: \begindocs{76} ! 3144: \section{Handling error conditions} ! 3145: Here are a bunch of uninteresting functions and modules ! 3146: that handle error conditions. ! 3147: \enddocs ! 3148: \begincode{77} ! 3149: \moddef{bad operator name}\endmoddef ! 3150: \{ ! 3151: print "unknown opcode", opname, "on line", NR > stderr ! 3152: next ! 3153: \} ! 3154: \endcode ! 3155: \begincode{78} ! 3156: \moddef{bad field name}\endmoddef ! 3157: \{ ! 3158: print "unknown field", $i, "on line", NR > stderr ! 3159: next ! 3160: \} ! 3161: \endcode ! 3162: \begincode{79} ! 3163: \moddef{BEGIN}\endmoddef ! 3164: stderr="/dev/tty" ! 3165: \endcode ! 3166: \begincode{80} ! 3167: \moddef{functions}\endmoddef ! 3168: function insist_fields(n) \{ ! 3169: if (NF != n) \{ ! 3170: print "Must have", n, "fields on line",NR ":", $0 > stderr ! 3171: return 0 ! 3172: \} else \{ ! 3173: return 1 ! 3174: \} ! 3175: \} ! 3176: \endcode ! 3177: \begindocs{81} ! 3178: \section{Leftover junk} ! 3179: Like a pack rat, I never throw out anything that might be useful again later. ! 3180: \enddocs ! 3181: \begincode{82} ! 3182: \moddef{junk}\endmoddef ! 3183: function thetype(n) \{ ! 3184: if (n==OPCODE) return "OPCODE" ! 3185: else if (n==SPECIAL) return "SPECIAL" ! 3186: else if (n==BCOND) return "BCOND" ! 3187: else if (n==COP1) return "COP1" ! 3188: else return "BADTYPE" ! 3189: \} ! 3190: \endcode ! 3191: \begincode{83} ! 3192: \moddef{decoding junk}\endmoddef ! 3193: for (f in fieldnames) \{ ! 3194: printf "^ \\"\\\\n%s = \\" ^ Integer.makestring %s\\n",f,f > decode ! 3195: \} ! 3196: printf "^\\"\\\\n\\"\\n" > decode ! 3197: \endcode ! 3198: \filename{/u/nr/sml/36/src/runtime/MIPS.prim.nw} ! 3199: \begindocs{0} ! 3200: \section{Assembly-language primitives for the run-time system} ! 3201: This file is derived from the similar file for the VAX. ! 3202: We include \code{}<regdef.h>\edoc{}, which defines names for the registers. ! 3203: \enddocs ! 3204: \begincode{1} ! 3205: \moddef{*}\endmoddef ! 3206: #include "tags.h" ! 3207: #include "prof.h" ! 3208: #include "ml.h" ! 3209: #include "prim.h" ! 3210: \LA{}register definitions\RA{} ! 3211: \LA{}\code{}String\edoc{} and \code{}Closure\edoc{} definitions\RA{} ! 3212: .data ! 3213: \LA{}data segment items\RA{} ! 3214: .text ! 3215: \LA{}run vector\RA{} ! 3216: \LA{}array\RA{} ! 3217: \LA{}string and bytearray\RA{} ! 3218: \LA{}C linkage\RA{} ! 3219: \LA{}calling C routines\RA{} ! 3220: \LA{}system calls\RA{} ! 3221: \LA{}floating point\RA{} ! 3222: /* this bogosity is for export.c */ ! 3223: .globl startptr ! 3224: startptr: .word __start /* just a guess... */ ! 3225: ! 3226: ! 3227: \endcode ! 3228: \begindocs{2} ! 3229: We define a couple of macros for creating strings and closures. ! 3230: When calling \code{}String\edoc{} we should use a literal string whose length ! 3231: is a multiple of~4. ! 3232: ! 3233: The closure of a primitive function ! 3234: is a record of length~1, containing a pointer to the first ! 3235: instruction in the function. ! 3236: All closures have length~1 because there aren't any free variables in any ! 3237: of the primitive functions. ! 3238: \enddocs ! 3239: \begincode{3} ! 3240: \moddef{\code{}String\edoc{} and \code{}Closure\edoc{} definitions}\endmoddef ! 3241: #define String(handle,len,str) .align 2;\\ ! 3242: .set noreorder;\\ ! 3243: .word len*power_tags+tag_string;\\ ! 3244: handle: .ascii str;\\ ! 3245: .set reorder ! 3246: #define Closure(name) .align 2;\\ ! 3247: .set noreorder;\\ ! 3248: .word mak_desc(1,tag_record);\\ ! 3249: name: .word 9f; /* address of routine */ \\ ! 3250: .word 1; /* here for historical reasons */\\ ! 3251: .word tag_backptr;\\ ! 3252: .set reorder;\\ ! 3253: 9: ! 3254: \endcode ! 3255: \begindocs{4} ! 3256: \subsection{Allocation and garbage collection} ! 3257: Put a brief summary here: gc is caused by storing beyond the end of high ! 3258: memory. ! 3259: For that reason we store the last word of objects first. ! 3260: ! 3261: \enddocs ! 3262: \begindocs{5} ! 3263: \subsection{Register usage} ! 3264: \input regs ! 3265: \enddocs ! 3266: \begincode{6} ! 3267: \moddef{register definitions}\endmoddef ! 3268: #define stdarg 2 ! 3269: #define stdcont 3 ! 3270: #define stdclos 4 ! 3271: #define storeptr 22 ! 3272: #define dataptr 23 ! 3273: #define exnptr 30 ! 3274: #define artemp1 24 ! 3275: #define artemp2 25 ! 3276: #define artemp3 20 ! 3277: #define ptrtemp 21 ! 3278: \endcode ! 3279: \begindocs{7} ! 3280: The MIPS version of Unix doesn't put underscores in front of global names. ! 3281: ! 3282: First we define the global \code{}runvec\edoc{}. ! 3283: This is an Ml object that represents the substructure \code{}A\edoc{} in ! 3284: {\tt boot/assembly.sig}. ! 3285: All the ML functions will call these primitives by grabbing them ! 3286: out of this record, which contains pointers to all the primitives. ! 3287: \enddocs ! 3288: \begincode{8} ! 3289: \moddef{run vector}\endmoddef ! 3290: ! 3291: .globl runvec ! 3292: .align 2 ! 3293: .word mak_desc(8,tag_record) ! 3294: runvec: ! 3295: .word array_v ! 3296: .word callc_v ! 3297: .word create_b_v ! 3298: .word create_s_v ! 3299: .word floor_v ! 3300: .word logb_v ! 3301: .word scalb_v ! 3302: .word syscall_v ! 3303: ! 3304: \endcode ! 3305: \begindocs{9} ! 3306: \subsection{Creating arrays, strings, and bytearrays} ! 3307: \code{}array(m,x)\edoc{} creates an array of length $n$, each element initialized ! 3308: to $x$. ! 3309: (The corresponding record creation code is not implemented as a primitive; ! 3310: the ML compiler generates that code in line.) ! 3311: $n$~is a tagged integer representing the length in words; ! 3312: $x$ can be any value. ! 3313: This routine will loop forever (or until something strange happens ! 3314: in memory) if $n<0$. ! 3315: ! 3316: We need to be careful in the implementation to make sure all register values ! 3317: are sensible when garbage collection might occur. ! 3318: ! 3319: If the order of instructions seems a little strange, it's because we try to ! 3320: make sensible use of load delay slots. ! 3321: \enddocs ! 3322: \begincode{10} ! 3323: \moddef{array}\endmoddef ! 3324: Closure(array_v) ! 3325: lw $artemp1,0($stdarg) /* tagged length in $artemp1 */ ! 3326: lw $10,4($stdarg) /* get initial value in $10 */ ! 3327: sra $artemp1,1 /* drop the tag bit */ ! 3328: sll $artemp2,$artemp1,width_tags /* length for descr into $artemp2 */ ! 3329: ori $artemp2,tag_array /* complete descriptor into $artemp2 */ ! 3330: sll $artemp1,2 /* get length in bytes into $artemp1 */ ! 3331: .set noreorder /* can't reorder because collection might occur */ ! 3332: add $artemp3,$artemp1,$dataptr /* $artemp3 points to last word ! 3333: of new array*/ ! 3334: badgc1: sw $0,($artemp3) /* clear; causes allocation */ ! 3335: .set reorder /* can rearrange instructions again */ ! 3336: \endcode ! 3337: \begincode{11} ! 3338: \moddef{load bad pc into \code{}$artemp2\edoc{}; branch to \code{}badpc\edoc{} if == \code{}$artemp1\edoc{}}\endmoddef ! 3339: la $artemp2,badgc1 ! 3340: beq $artemp1,$artemp2,badpc ! 3341: \endcode ! 3342: \begindocs{12} ! 3343: At this point garbage collection may have occurred. ! 3344: Ordinarily, we couldn't rely ! 3345: on the value in \code{}$artemp3\edoc{}, because it's not forwarded. ! 3346: However, this is one of the special garbage collection locations, ! 3347: so we do know that \code{}$artemp3\edoc{} is sensible. ! 3348: But, since we really want something larger, we recompute it, ! 3349: using the (possibly changed) value of the data pointer. ! 3350: Extra cleverness here might enable us to save one instruction. ! 3351: \enddocs ! 3352: \begincode{13} ! 3353: \moddef{array}\endmoddef ! 3354: sw $artemp2,0($dataptr) /* store the descriptor */ ! 3355: add $dataptr,4 /* points to new object */ ! 3356: add $artemp3,$artemp1,$dataptr /* beyond last word of new array*/ ! 3357: add $stdarg,$dataptr,$0 /* put ptr in return register ! 3358: (return val = arg of continuation) */ ! 3359: \LA{}store the initial value in every slot, leaving \code{}$dataptr\edoc{} pointing to the first free word\RA{} ! 3360: lw $10,0($stdcont) /* grab continuation */ ! 3361: j $10 /* return */ ! 3362: ! 3363: \endcode ! 3364: \begindocs{14} ! 3365: With some clever thinking, the size of this loop could probably be cut ! 3366: from four instructions to three instructions. ! 3367: \enddocs ! 3368: \begincode{15} ! 3369: \moddef{store the initial value in every slot, leaving \code{}$dataptr\edoc{} pointing to the first free word}\endmoddef ! 3370: b 2f ! 3371: 1: sw $10,0($dataptr) /* store the value */ ! 3372: addi $dataptr,4 /* on to the next word */ ! 3373: 2: bne $dataptr,$artemp3,1b /* if not off the end, repeat */ ! 3374: ! 3375: ! 3376: \endcode ! 3377: \begindocs{16} ! 3378: \code{}create_b(n)\edoc{} creates a byte-array of length $n$, and ! 3379: \code{}create_s(n)\edoc{} creates a string of length $n$. ! 3380: ! 3381: We use the same code to create byte arrays and strings, since the only ! 3382: difference is in the tags. ! 3383: The odd arrangement of closures (odd because each one starts a new record) ! 3384: causes no problems because this code isn't in the garbage-collectible region. ! 3385: \enddocs ! 3386: \begincode{17} ! 3387: \moddef{string and bytearray}\endmoddef ! 3388: Closure(create_b_v) ! 3389: addi $artemp3,$0,tag_bytearray /* tag into $artemp3 */ ! 3390: b 2f ! 3391: Closure(create_s_v) ! 3392: addi $artemp3,$0,tag_string /* tag into $artemp3 */ ! 3393: 2: ! 3394: \endcode ! 3395: \begindocs{18} ! 3396: The length computation may be a bit confusing. ! 3397: We are handed a tagged integer $2n+1$, and we need to compute the required ! 3398: number of words, which is $\lfloor{n+3\over 4}\rfloor$. ! 3399: This is just $\lfloor{(2n+1)+5\over 8}\rfloor$. ! 3400: However, we'll save an instruction later if we happen to have one more than ! 3401: the number of words tucked away in a register, ! 3402: because $1+\lfloor{n+3\over 4}\rfloor$ is the number of words ! 3403: we're taking from the data space (we include the descriptor). ! 3404: So we compute $(2n+1)+13$ and continue accordingly ! 3405: \enddocs ! 3406: \begincode{19} ! 3407: \moddef{string and bytearray}\endmoddef ! 3408: addi $artemp1,$stdarg,13 /* $2n+14$ */ ! 3409: sra $artemp1,3 /* number of words in string+tag */ ! 3410: sll $artemp1,2 /* # of bytes allocated for str+tag */ ! 3411: .set noreorder /* don't cross gc boundary */ ! 3412: add $artemp2,$artemp1,$dataptr /* beyond last word of string */ ! 3413: badgc2: sw $0,-4($artemp2) /* clear last; causes allocation */ ! 3414: .set reorder ! 3415: sra $artemp2,$stdarg,1 /* untagged length in bytes */ ! 3416: sll $artemp2,width_tags /* room for descriptor */ ! 3417: or $artemp2,$artemp3 /* descriptor */ ! 3418: sw $artemp2,0($dataptr) /* store descriptor */ ! 3419: addi $stdarg,$dataptr,4 /* pointer to new string */ ! 3420: add $dataptr,$artemp1 /* advance; save 1 instruction */ ! 3421: lw $10,0($stdcont) /* grab continuation */ ! 3422: j $10 /* return */ ! 3423: ! 3424: \endcode ! 3425: \begincode{20} ! 3426: \moddef{load bad pc into \code{}$artemp2\edoc{}; branch to \code{}badpc\edoc{} if == \code{}$artemp1\edoc{}}\endmoddef ! 3427: la $artemp2,badgc2 ! 3428: beq $artemp1,$artemp2,badpc ! 3429: ! 3430: \endcode ! 3431: \begindocs{21} ! 3432: \subsection{Linkage with C code} ! 3433: C always gains control first, and stuffs something appropriate into ! 3434: the register save areas before starting ML by calling \code{}restoreregs\edoc{}. ! 3435: It also puts something appropriate in the ML \code{}saved_pc\edoc{}. ! 3436: \code{}restoreregs\edoc{} squirrels away the current state of the C runtime stack, ! 3437: restores the ML registers, and finally jumps to the saved program counter. ! 3438: ! 3439: When ML wants to call C, it calls \code{}saveregs\edoc{}, which saves the ML state ! 3440: in the appropriate save areas, then restores the C runtime stack and returns. ! 3441: Before returning to C, it sets \code{}cause\edoc{} to something appropriate. ! 3442: ! 3443: All programs must ensure that \code{}restoreregs\edoc{} {\em never} calls itself ! 3444: recursively, because it is {\em not} reentrant. ! 3445: ! 3446: The C end of this connection is on display in the \code{}runML()\edoc{} function of ! 3447: \code{}~ml/src/runtime/callgc.c\edoc{}. ! 3448: \enddocs ! 3449: \begincode{22} ! 3450: \moddef{data segment items}\endmoddef ! 3451: bottom: .word 0 /* C's saved stack pointer */ ! 3452: \endcode ! 3453: \begincode{23} ! 3454: \moddef{C linkage}\endmoddef ! 3455: .globl saveregs ! 3456: .globl handle_c ! 3457: .globl return_c ! 3458: .globl restoreregs ! 3459: .ent restoreregs ! 3460: restoreregs: ! 3461: \LA{}save caller's stuff using MIPS calling conventions\RA{} ! 3462: \LA{}enable floating point overflow and zerodivide exceptions\RA{} ! 3463: sw $sp,bottom /* save C's stack pointer */ ! 3464: \LA{}if \code{}saved_pc\edoc{} points to a bad spot, adjust it (destroys arithmetic temps)\RA{} ! 3465: \LA{}restore the ML registers\RA{} ! 3466: .set noat /* This trick will cause a warning, but the code is OK */ ! 3467: lw $at,saved_pc /* grab the saved program counter */ ! 3468: j $at /* and continue executing at that spot */ ! 3469: .set at ! 3470: ! 3471: \endcode ! 3472: \begindocs{24} ! 3473: The next two functions are an exception handler and a continuation for ! 3474: ML programs called from C. ! 3475: Although neither appears to return any result (by manipulating \code{}$stdarg\edoc{}, ! 3476: they do return results. ! 3477: It's just that the C code on the other end gets the result out of ! 3478: \code{}saved_ptrs[0],\edoc{} where it expects to find \code{}$stdarg\edoc{}. ! 3479: \enddocs ! 3480: \begincode{25} ! 3481: \moddef{C linkage}\endmoddef ! 3482: Closure(handle_c) /* exception handler for ML functions called from C */ ! 3483: li $artemp1,CAUSE_EXN ! 3484: sw $artemp1,cause ! 3485: b saveregs ! 3486: Closure(return_c) /* continuation for ML functions called from C */ ! 3487: li $artemp1,CAUSE_RET ! 3488: sw $artemp1,cause ! 3489: saveregs: ! 3490: \LA{}save the ML registers\RA{} ! 3491: lw $sp,bottom /* recover C's stack pointer */ ! 3492: \LA{}restore caller's stuff using MIPS calling conventions\RA{} ! 3493: j $31 /* return to C program */ ! 3494: .end restoreregs ! 3495: ! 3496: \endcode ! 3497: \begincode{26} ! 3498: \moddef{enable floating point overflow and zerodivide exceptions}\endmoddef ! 3499: .set noat ! 3500: cfc1 $at,$31 /* grab fpa control register */ ! 3501: ori $at,$at,0x600 /* set O and Z bits */ ! 3502: ctc1 $at,$31 /* return fpa control register */ ! 3503: .set at ! 3504: ! 3505: \endcode ! 3506: \begindocs{27} ! 3507: The MIPS calling conventions are described in gory detail in Appendix~D ! 3508: of the MIPS book; pages D-18 and following. ! 3509: ! 3510: At the moment we don't save any floating point registers. ! 3511: We save (on the stack) nine general-purpose registers, the global pointer, ! 3512: and the return address. ! 3513: ! 3514: We always have to allocate at least 16 bytes for argument build, ! 3515: because any C function might be varargs, and might begin by ! 3516: spilling all of its registers into the argument build area (Hanson). ! 3517: We allocate exactly sixteen bytes, planning to fiddle the stack if ! 3518: (God forbid) we are ever asked to issue a system call with more than ! 3519: 16 bytes worth of arguments. ! 3520: ! 3521: \enddocs ! 3522: \begincode{28} ! 3523: \moddef{save caller's stuff using MIPS calling conventions}\endmoddef ! 3524: #define regspace 44 ! 3525: #define localspace 4 ! 3526: #define argbuild 16 ! 3527: #define framesize (regspace+localspace+argbuild) /* must be multiple of 8 */ ! 3528: #define frameoffset (0-localspace) ! 3529: subu $sp,framesize ! 3530: \LA{}give .mask and save the C registers\RA{} ! 3531: ! 3532: \endcode ! 3533: \begincode{29} ! 3534: \moddef{restore caller's stuff using MIPS calling conventions}\endmoddef ! 3535: \LA{}restore the C registers\RA{} ! 3536: addu $sp,framesize ! 3537: \endcode ! 3538: \begindocs{30} ! 3539: We don't save floating point regs yet. ! 3540: \enddocs ! 3541: \begincode{31} ! 3542: \moddef{give .mask and save the C registers}\endmoddef ! 3543: .mask 0xd0ff0000,0-localspace ! 3544: sw $31,argbuild+40($sp) ! 3545: sw $30,argbuild+36($sp) ! 3546: sw $gp,argbuild+32($sp) ! 3547: sw $23,argbuild+28($sp) ! 3548: sw $22,argbuild+24($sp) ! 3549: sw $21,argbuild+20($sp) ! 3550: sw $20,argbuild+16($sp) ! 3551: sw $19,argbuild+12($sp) ! 3552: sw $18,argbuild+8($sp) ! 3553: sw $17,argbuild+4($sp) ! 3554: sw $16,argbuild($sp) ! 3555: \endcode ! 3556: \begincode{32} ! 3557: \moddef{restore the C registers}\endmoddef ! 3558: lw $31,argbuild+40($sp) ! 3559: lw $30,argbuild+36($sp) ! 3560: lw $gp,argbuild+32($sp) ! 3561: lw $23,argbuild+28($sp) ! 3562: lw $22,argbuild+24($sp) ! 3563: lw $21,argbuild+20($sp) ! 3564: lw $20,argbuild+16($sp) ! 3565: lw $19,argbuild+12($sp) ! 3566: lw $18,argbuild+8($sp) ! 3567: lw $17,argbuild+4($sp) ! 3568: lw $16,argbuild($sp) ! 3569: ! 3570: ! 3571: \endcode ! 3572: \begindocs{33} ! 3573: There are two save areas; one for pointers and one for non-pointers. ! 3574: (The pointer area may, of course, include tagged integers.) ! 3575: The pointer area has special spots for standard argument, continuation, ! 3576: and closure. ! 3577: In addition there are special save areas for the special registers. ! 3578: Register 31 is to be maintained constant relative to the program counter, ! 3579: so we store the difference with \code{}saved_pc\edoc{}. ! 3580: \enddocs ! 3581: \begincode{34} ! 3582: \moddef{save the ML registers}\endmoddef ! 3583: /* needn't save $1 */ ! 3584: /* the big three: argument, continuation, closure */ ! 3585: sw $stdarg,saved_ptrs ! 3586: sw $stdcont,saved_ptrs+4 ! 3587: sw $stdclos,saved_ptrs+8 ! 3588: ! 3589: /* All the miscellaneous guys */ ! 3590: sw $5,saved_ptrs+12 ! 3591: sw $6,saved_ptrs+16 ! 3592: sw $7,saved_ptrs+20 ! 3593: sw $8,saved_ptrs+24 ! 3594: sw $9,saved_ptrs+28 ! 3595: sw $10,saved_ptrs+32 ! 3596: sw $11,saved_ptrs+36 ! 3597: sw $12,saved_ptrs+40 ! 3598: sw $13,saved_ptrs+44 ! 3599: sw $14,saved_ptrs+48 ! 3600: sw $15,saved_ptrs+52 ! 3601: sw $16,saved_ptrs+56 ! 3602: sw $17,saved_ptrs+60 ! 3603: sw $18,saved_ptrs+64 ! 3604: sw $19,saved_ptrs+68 ! 3605: ! 3606: sw $21, saved_ptrs+72 ! 3607: ! 3608: sw $artemp1,saved_nonptrs ! 3609: sw $artemp2,saved_nonptrs+4 ! 3610: sw $artemp3,saved_nonptrs+8 ! 3611: ! 3612: /* don't touch registers $26 and $27 */ ! 3613: ! 3614: sw $storeptr,saved_storeptr ! 3615: sw $dataptr,saved_dataptr ! 3616: sw $exnptr,saved_exnptr ! 3617: ! 3618: \LA{}save $\code{}$31\edoc{}-\code{}saved_pc\edoc{}$ in \code{}saved_pc_diff\edoc{} (destroys \code{}$artemp1\edoc{})\RA{} ! 3619: ! 3620: ! 3621: \endcode ! 3622: \begincode{35} ! 3623: \moddef{restore the ML registers}\endmoddef ! 3624: /* the big three: argument, continuation, closure */ ! 3625: lw $stdarg,saved_ptrs ! 3626: lw $stdcont,saved_ptrs+4 ! 3627: lw $stdclos,saved_ptrs+8 ! 3628: ! 3629: /* All the miscellaneous guys */ ! 3630: lw $5,saved_ptrs+12 ! 3631: lw $6,saved_ptrs+16 ! 3632: lw $7,saved_ptrs+20 ! 3633: lw $8,saved_ptrs+24 ! 3634: lw $9,saved_ptrs+28 ! 3635: lw $10,saved_ptrs+32 ! 3636: lw $11,saved_ptrs+36 ! 3637: lw $12,saved_ptrs+40 ! 3638: lw $13,saved_ptrs+44 ! 3639: lw $14,saved_ptrs+48 ! 3640: lw $15,saved_ptrs+52 ! 3641: lw $16,saved_ptrs+56 ! 3642: lw $17,saved_ptrs+60 ! 3643: lw $18,saved_ptrs+64 ! 3644: lw $19,saved_ptrs+68 ! 3645: ! 3646: lw $21, saved_ptrs+72 ! 3647: ! 3648: \LA{}restore \code{}$31\edoc{} from \code{}saved_pc\edoc{} \& \code{}saved_pc_diff\edoc{} (destroys \code{}$artemp1\edoc{})\RA{} ! 3649: lw $artemp1,saved_nonptrs ! 3650: lw $artemp2,saved_nonptrs+4 ! 3651: lw $artemp3,saved_nonptrs+8 ! 3652: ! 3653: /* don't touch registers $26 and $27 */ ! 3654: ! 3655: lw $storeptr,saved_storeptr ! 3656: lw $dataptr,saved_dataptr ! 3657: lw $exnptr,saved_exnptr ! 3658: ! 3659: \endcode ! 3660: \begincode{36} ! 3661: \moddef{save $\code{}$31\edoc{}-\code{}saved_pc\edoc{}$ in \code{}saved_pc_diff\edoc{} (destroys \code{}$artemp1\edoc{})}\endmoddef ! 3662: lw $artemp1,saved_pc ! 3663: subu $artemp1,$31,$artemp1 /* mustn't overflow */ ! 3664: sw $artemp1,saved_pc_diff ! 3665: \endcode ! 3666: \begincode{37} ! 3667: \moddef{restore \code{}$31\edoc{} from \code{}saved_pc\edoc{} \& \code{}saved_pc_diff\edoc{} (destroys \code{}$artemp1\edoc{})}\endmoddef ! 3668: lw $artemp1,saved_pc ! 3669: lw $31,saved_pc_diff ! 3670: addu $31,$artemp1 /* mustn't overflow */ ! 3671: \endcode ! 3672: \begincode{38} ! 3673: \moddef{data segment items}\endmoddef ! 3674: saved_pc_diff: .word 0 ! 3675: ! 3676: ! 3677: \endcode ! 3678: \begindocs{39} ! 3679: Because the Mips has no indexed addressing modes, there are special ! 3680: circumstances under which we have to adjust the program counter before ! 3681: a garbage collection. ! 3682: The problem arises when we want to create an object whose size is not ! 3683: known at compile time. ! 3684: In order to do that, we have to add the size of the object to \code{}$dataptr\edoc{}, ! 3685: putting the result in a new register. ! 3686: We then store at offset $-4$ from that register to allocate (and possibly ! 3687: cause garbage collection). ! 3688: That register can't be a pointer, because at the time of the gc it doesn't ! 3689: point to anything sensible (in fact, by definition it points out of the ! 3690: garbage-collectible region entirely). ! 3691: If it is a nonpointer, though, it isn't changed by the garbage collection, ! 3692: so when the collection is over, we attempt once again to store in exactly ! 3693: the same place, causing another fault (unless the heap has been resized). ! 3694: ! 3695: The solution is a hack. Since there are only two places this problem ! 3696: can occur, we check \code{}saved_pc\edoc{} against the offending program counters. ! 3697: If we find one, we reduce \code{}saved_pc\edoc{} by 4 (the size of one instruction), ! 3698: causing the addition to be repeated. ! 3699: ! 3700: \enddocs ! 3701: \begincode{40} ! 3702: \moddef{if \code{}saved_pc\edoc{} points to a bad spot, adjust it (destroys arithmetic temps)}\endmoddef ! 3703: lw $artemp1,saved_pc ! 3704: \LA{}load bad pc into \code{}$artemp2\edoc{}; branch to \code{}badpc\edoc{} if == \code{}$artemp1\edoc{}\RA{} ! 3705: b 1f ! 3706: badpc: ! 3707: subu $artemp1,4 /* adjust */ ! 3708: sw $artemp1,saved_pc /* save */ ! 3709: 1: ! 3710: ! 3711: ! 3712: \endcode ! 3713: \begindocs{41} ! 3714: \code{}callc(f,a)\edoc{} calls a C-language function \code{}f\edoc{} with argument \code{}a\edoc{}. ! 3715: We don't have to save a register unless we'll need its value later. ! 3716: ! 3717: The closure of this routine is irrelevant, since \code{}callc\edoc{} doesn't ! 3718: have any free variables. ! 3719: Therefore the only things that have to be restored after the call to~C ! 3720: are the continuation, the store pointer, the data pointer, and ! 3721: the exception handler. ! 3722: If we wanted \code{}callc\edoc{} to be more efficient, we would ! 3723: rearrange things so that all those registers fell into \code{}s0\edoc{}--\code{}s8\edoc{}, ! 3724: where they would automatically be preserved across procedure calls. ! 3725: As it stands, everything except the continuation is preserved, ! 3726: so we're not doing too badly. ! 3727: ! 3728: Miraculously, C routines return integer results in \code{}$2\edoc{}, which is ! 3729: exactly the register we need to pass to our continuation (in order to ! 3730: return a value). ! 3731: I decided not to rely on this, and to include a \code{}move\edoc{} instruction ! 3732: anyway. Maybe the assembler will park it in a delay slot since it ! 3733: is a nop. ! 3734: \enddocs ! 3735: \begincode{42} ! 3736: \moddef{calling C routines}\endmoddef ! 3737: Closure(callc_v) ! 3738: sw $stdcont,argbuild+regspace($sp) /* save continuation on stack */ ! 3739: lw $4,4($stdarg) /* get value a into arg register */ ! 3740: lw $10,0($stdarg) /* get address of f into misc reg */ ! 3741: jal $10 /* call f ($31 can be trashed) */ ! 3742: move $stdarg,$2 /* return val is argument to continuation */ ! 3743: lw $stdcont,argbuild+regspace($sp) /* recover continuation */ ! 3744: \LA{}put zeroes in all forwardable regs that might hold garbage\RA{} ! 3745: lw $artemp3,cause /* get cause */ ! 3746: bne $artemp3,$0,saveregs /* if cause != 0, save ML & return to C */ ! 3747: lw $10,0($stdcont) /* grab continuation */ ! 3748: j $10 /* return */ ! 3749: \endcode ! 3750: \begindocs{43} ! 3751: A forwardable register can hold garbage unless it was saved ! 3752: by C (is in \code{}s0\edoc{}--\code{}s8\edoc{}) or is \code{}$stdarg\edoc{} of \code{}$stdcont\edoc{}. ! 3753: \enddocs ! 3754: \begincode{44} ! 3755: \moddef{put zeroes in all forwardable regs that might hold garbage}\endmoddef ! 3756: move $stdclos,$0 ! 3757: move $5,$0 ! 3758: move $6,$0 ! 3759: move $7,$0 ! 3760: move $8,$0 ! 3761: move $9,$0 ! 3762: move $10,$0 ! 3763: move $11,$0 ! 3764: move $12,$0 ! 3765: move $13,$0 ! 3766: move $14,$0 ! 3767: move $15,$0 ! 3768: /* $16--$23 and $30 are saved by the callee */ ! 3769: ! 3770: \endcode ! 3771: \begindocs{45} ! 3772: This interface is going to be agony, because the rules for passing ! 3773: arguments are passing strange. ! 3774: The interface is \code{}syscall_v(callnumber,argvector,argcount)\edoc{}. ! 3775: ! 3776: The system call interface is the same as the procedure call interface, ! 3777: but instead of a \code{}jal\edoc{} we use a \code{}syscall\edoc{} instruction, and ! 3778: we put the system call number in register \code{}$2\edoc{}. ! 3779: It appears that, after the execution of the \code{}syscall\edoc{} handler, ! 3780: the result is in \code{}$2\edoc{}, and \code{}$7\edoc{} is zero unless an error occurred. ! 3781: We will put all the arguments on the stack, then load the first four ! 3782: into \code{}$4\edoc{}--\code{}$7\edoc{}. ! 3783: \enddocs ! 3784: \begincode{46} ! 3785: \moddef{system calls}\endmoddef ! 3786: Closure(syscall_v) ! 3787: sw $stdcont,argbuild+regspace($sp) /* save continuation on stack */ ! 3788: lw $artemp1,8($stdarg) /* 2*argc+1 in $artemp1 */ ! 3789: sra $artemp1,1 /* argc in $artemp1 */ ! 3790: move $16,$sp /* save our $sp */ ! 3791: \LA{}extend argbuild area to be big enough for all arguments\RA{} ! 3792: lw $ptrtemp,4($stdarg) /* argv in $ptrtemp */ ! 3793: \LA{}put all arguments onto the stack\RA{} ! 3794: \LA{}load first four arguments into \code{}$4\edoc{}--\code{}$7\edoc{}\RA{} ! 3795: 9: lw $2,0($stdarg) /* get syscall # in $2; trash $stdarg */ ! 3796: sra $2,1 /* throw out the tag bit */ ! 3797: syscall ! 3798: move $sp,$16 /* recover the good stack pointer */ ! 3799: lw $stdcont,argbuild+regspace($sp) /* recover continuation */ ! 3800: bnez $7,1f /* if error, return ~1 */ ! 3801: move $stdarg,$2 /* return val is argument to continuation */ ! 3802: add $stdarg,$stdarg /* double return value */ ! 3803: addi $stdarg,1 /* and add tag bit */ ! 3804: b 2f ! 3805: 1: li $stdarg,-1 ! 3806: 2: ! 3807: \LA{}put zeroes in all forwardable regs that might hold garbage\RA{} ! 3808: lw $10,0($stdcont) /* grab continuation */ ! 3809: j $10 /* return */ ! 3810: ! 3811: \endcode ! 3812: \begindocs{47} ! 3813: At this point we know that the number of arguments is in \code{}$artemp1\edoc{}. ! 3814: We have room for four arguments; if there are more ! 3815: we'll have to increase the stack size by the appropriate multiple of 8 ! 3816: so that it stays doubleword-aligned. ! 3817: \enddocs ! 3818: \begincode{48} ! 3819: \moddef{extend argbuild area to be big enough for all arguments}\endmoddef ! 3820: ble $artemp1,4,1f /* big enough */ ! 3821: sub $artemp2,$artemp1,3 /* (temp2 = argc - 4 + 1) > 1 */ ! 3822: sra $artemp2,1 ! 3823: sll $artemp2,3 /* temp2 = 4 * roundup (argc-4,2) */ ! 3824: subu $sp,$artemp2 /* increase stack */ ! 3825: 1: ! 3826: ! 3827: \endcode ! 3828: \begindocs{49} ! 3829: Now we have a list of arguments pointed to by \code{}$ptrtemp\edoc{}. ! 3830: We have the count of the arguments in \code{}$artemp1\edoc{}. ! 3831: We have to put them on the stack. ! 3832: We have to remove tag bits where appropriate. ! 3833: \enddocs ! 3834: \begincode{50} ! 3835: \moddef{put all arguments onto the stack}\endmoddef ! 3836: move $artemp2,$sp /* destination in $artemp2 */ ! 3837: b 1f /* branch forward to test */ ! 3838: 2: /* argc > 0 */ ! 3839: lw $artemp3,0($ptrtemp) /* get list element */ ! 3840: andi $10,$artemp3,1 /* tagged? */ ! 3841: beqz $10,3f ! 3842: sra $artemp3,1 /* drop tag bit */ ! 3843: 3: sw $artemp3,0($artemp2) /* save the argument */ ! 3844: lw $ptrtemp,4($ptrtemp) /* next element */ ! 3845: add $artemp2,4 /* next arg build area */ ! 3846: sub $artemp1,1 /* --argc */ ! 3847: 1: bgtz $artemp1,2b /* if argc>0, store another */ ! 3848: ! 3849: \endcode ! 3850: \begindocs{51} ! 3851: It doesn't matter if we load arguments that aren't there; the ! 3852: system call will just ignore them. ! 3853: \enddocs ! 3854: \begincode{52} ! 3855: \moddef{load first four arguments into \code{}$4\edoc{}--\code{}$7\edoc{}}\endmoddef ! 3856: lw $4,0($sp) ! 3857: lw $5,4($sp) ! 3858: lw $6,8($sp) ! 3859: lw $7,12($sp) ! 3860: ! 3861: \endcode ! 3862: \begindocs{53} ! 3863: \subsection{Floating point} ! 3864: We store floating point constants in two words, with the least significant ! 3865: word first. ! 3866: We use the 64 bit IEEE format. ! 3867: ! 3868: We begin with instructions to change the rounding modes. ! 3869: See the MIPS book, pages 6-5--6-7. ! 3870: \enddocs ! 3871: \begincode{54} ! 3872: \moddef{tell the floating point unit to round toward $-\infty$}\endmoddef ! 3873: .set noat ! 3874: cfc1 $at,$31 /* grab fpa control register */ ! 3875: ori $at,0x03 /* set rounding bits to 11 */ ! 3876: ctc1 $at,$31 /* return fpa control register */ ! 3877: .set at ! 3878: \endcode ! 3879: \begincode{55} ! 3880: \moddef{tell the floating point unit to round to nearest}\endmoddef ! 3881: .set noat ! 3882: cfc1 $at,$31 /* grab fpa control register */ ! 3883: ori $at,0x03 /* set rounding bits to 11 */ ! 3884: xori $at,0x03 /* set rounding bits to 00 ! 3885: ctc1 $at,$31 /* return fpa control register */ ! 3886: .set at ! 3887: \endcode ! 3888: \begindocs{56} ! 3889: These floating point functions are used int floating to integer conversion. ! 3890: \enddocs ! 3891: \begincode{57} ! 3892: \moddef{floating point}\endmoddef ! 3893: /* Floating exceptions raised (assuming ROP's are never passed to functions): ! 3894: * DIVIDE BY ZERO - (div) ! 3895: * OVERFLOW/UNDERFLOW - (add,div,sub,mul) as appropriate ! 3896: * ! 3897: * floor raises integer overflow if the float is out of 32-bit range, ! 3898: * so the float is tested before conversion, to make sure it is in (31-bit) ! 3899: * range */ ! 3900: ! 3901: \endcode ! 3902: \begindocs{58} ! 3903: \code{}floor(x)\edoc{} returns the smallest integer less than or equal to \code{}x\edoc{}. ! 3904: \enddocs ! 3905: \begincode{59} ! 3906: \moddef{floating point}\endmoddef ! 3907: Closure(floor_v) ! 3908: lwc1 $f4,0($stdarg) /* get least significant word */ ! 3909: lwc1 $f5,4($stdarg) /* get most significant word */ ! 3910: \LA{}tell the floating point unit to round toward $-\infty$\RA{} ! 3911: cvt.w.d $f6,$f4 /* convert to integer */ ! 3912: \LA{}tell the floating point unit to round to nearest\RA{} ! 3913: mfc1 $stdarg,$f6 /* get in std argument register */ ! 3914: sll $stdarg,1 /* make room for tag bit */ ! 3915: add $stdarg,1 /* add the tag bit */ ! 3916: lw $10,0($stdcont) /* grab continuation */ ! 3917: j $10 /* return */ ! 3918: ! 3919: ! 3920: \endcode ! 3921: \begindocs{60} ! 3922: \code{}logb(x)\edoc{} returns the exponent part of the floating point \code{}x\edoc{}. ! 3923: We grab the 11-bit exponent from the word, then unbias it (according ! 3924: to the IEEE standard) by subtracting 1023. ! 3925: \enddocs ! 3926: \begincode{61} ! 3927: \moddef{floating point}\endmoddef ! 3928: Closure(logb_v) ! 3929: lw $stdarg,4($stdarg) /* most significant part */ ! 3930: srl $stdarg,20 /* throw out 20 low bits */ ! 3931: andi $stdarg,0x07ff /* clear all but 11 low bits */ ! 3932: sub $stdarg,1023 /* subtract 1023 */ ! 3933: sll $stdarg,1 /* make room for tag bit */ ! 3934: add $stdarg,1 /* add the tag bit */ ! 3935: lw $10,0($stdcont) /* grab continuation */ ! 3936: j $10 /* return */ ! 3937: ! 3938: \endcode ! 3939: \begindocs{62} ! 3940: \code{}scalb(x,n)\edoc{} adds \code{}n\edoc{} to the exponent of floating ! 3941: point \code{}x\edoc{}. ! 3942: Since we don't want the resulting float to be anything ! 3943: special, we insist that the unbiased exponent of the result ! 3944: satisfy $-1022 \le E \le 1023$, i.e.\ that the biased exponent satisfy ! 3945: $1 \le e \le 2046$. ! 3946: \enddocs ! 3947: \begincode{63} ! 3948: \moddef{floating point}\endmoddef ! 3949: Closure(scalb_v) ! 3950: lw $artemp1,4($stdarg) /* get tagged n */ ! 3951: sra $artemp1,1 /* get real n */ ! 3952: beqz $artemp1,9f /* if zero, return the old float */ ! 3953: lw $ptrtemp,0($stdarg) /* get pointer to float */ ! 3954: lw $artemp2,4($ptrtemp) /* most significant part */ ! 3955: srl $artemp2,20 /* throw out 20 low bits */ ! 3956: andi $artemp2,0x07ff /* clear all but 11 low bits */ ! 3957: add $artemp3,$artemp2,$artemp1 /* new := old + n */ ! 3958: blt $artemp3,1,under /* punt if underflow */ ! 3959: bgt $artemp3,2046,over /* or overflow */ ! 3960: \LA{}allocate and store new floating point constant and set \code{}$stdarg\edoc{}\RA{} ! 3961: lw $10,0($stdcont) /* grab continuation */ ! 3962: j $10 /* return */ ! 3963: ! 3964: 9: lw $stdarg,0($stdarg) /* get old float */ ! 3965: lw $10,0($stdcont) /* grab continuation */ ! 3966: j $10 /* return */ ! 3967: ! 3968: over: la $stdarg,1f /* exception name in $stdarg */ ! 3969: b raise_real ! 3970: String(1,8,"overflow") ! 3971: under: la $stdarg,1f /* exception name in $stdarg */ ! 3972: b raise_real ! 3973: String(1,9,"underflow\\0\\0\\0") ! 3974: ! 3975: raise_real: ! 3976: /* build new record to pass to exception handler */ ! 3977: /* [descriptor] ! 3978: /* [exception (string)] ! 3979: /* [real_e (more exception info)] ! 3980: */ ! 3981: la $10,real_e /* get address of real_e */ ! 3982: .set noreorder ! 3983: sw $10,8($dataptr) /* allocate; may cause gc */ ! 3984: .set reorder ! 3985: sw $stdarg,4($dataptr) ! 3986: li $10,mak_desc(2,tag_record) ! 3987: sw $10,0($dataptr) ! 3988: add $stdarg,$dataptr,4 /* new record is argument */ ! 3989: addi $dataptr,12 /* $dataptr restored */ ! 3990: move $stdclos,$exnptr /* make sure closure is right */ ! 3991: lw $10,0($exnptr) /* grab handler */ ! 3992: j $10 /* raise the exception */ ! 3993: ! 3994: \endcode ! 3995: \begindocs{64} ! 3996: Here we indulge in a little cleverness to save a couple of instructions. ! 3997: Since the old value is in \code{}$artemp2\edoc{} and the new in \code{}$artemp3\edoc{}, ! 3998: we can \code{}xor\edoc{} them, then store the new one with a second \code{}xor\edoc{}. ! 3999: \enddocs ! 4000: \begincode{65} ! 4001: \moddef{allocate and store new floating point constant and set \code{}$stdarg\edoc{}}\endmoddef ! 4002: xor $artemp3,$artemp2 /* at3 = new xor old */ ! 4003: sll $artemp3,20 /* put exponent in right position */ ! 4004: lw $artemp2,4($ptrtemp) /* most significant word */ ! 4005: xor $artemp2,$artemp3 /* change to new exponent */ ! 4006: .set noreorder ! 4007: sw $artemp2,8($dataptr) /* allocate; may cause gc */ ! 4008: .set reorder ! 4009: lw $artemp2,0($ptrtemp) /* get least significant word */ ! 4010: li $10,mak_desc(8,tag_string) /* make descriptor */ ! 4011: sw $artemp2,4($dataptr) /* save lsw */ ! 4012: sw $10,0($dataptr) /* save descriptor */ ! 4013: add $stdarg,$dataptr,4 /* get pointer to new float */ ! 4014: add $dataptr,12 /* point to new free word */ ! 4015: \endcode ! 4016: \bye
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.