riscv dialects

import%20marimo%0A%0A__generated_with%20%3D%20%220.23.15%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Aasync%20def%20_()%3A%0A%20%20%20%20%23%20Get%20the%20current%20notebook%20URL%2C%20drop%20the%20'blob'%20URL%20components%20that%20seem%20to%20be%20added%2C%0A%20%20%20%20%23%20and%20add%20the%20buildnumber%20that%20a%20makethedocs%20PR%20build%20seems%20to%20add.%20This%20allows%20to%20load%0A%20%20%20%20%23%20the%20wheel%20both%20locally%20and%20when%20deployed%20to%20makethedocs.%0A%20%20%20%20async%20def%20import_xdsl()%3A%0A%20%20%20%20%20%20%20%20import%20re%0A%20%20%20%20%20%20%20%20from%20urllib.parse%20import%20urlparse%0A%0A%20%20%20%20%20%20%20%20import%20micropip%0A%20%20%20%20%20%20%20%20from%20marimo%20import%20notebook_location%0A%0A%20%20%20%20%20%20%20%20url%20%3D%20str(notebook_location()).replace(%22blob%3A%22%2C%20%22%22)%0A%20%20%20%20%20%20%20%20print(f%22DEBUG%3A%20notebook%20url%20(full)%3A%20%7Burl%7D%22)%0A%0A%20%20%20%20%20%20%20%20url_parsed%20%3D%20urlparse(url)%0A%20%20%20%20%20%20%20%20scheme%20%3D%20url_parsed.scheme%0A%20%20%20%20%20%20%20%20netloc%20%3D%20url_parsed.netloc%0A%0A%20%20%20%20%20%20%20%20print(f%22DEBUG%3A%20notebook%20url%20(parsed)%3A%20%7Burl_parsed%7D%22)%0A%0A%20%20%20%20%20%20%20%20url%20%3D%20re.sub(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22(%5B%5E%2F%5D)%2F(%5Ba-f0-9-%5D%2B-%5Ba-f0-9-%5D%2B-%5Ba-f0-9-%5D%2B-%5Ba-f0-9-%5D%2B)%22%2C%20%22%5C%5C1%2F%22%2C%20url%2C%20count%3D1%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20buildnumber%20%3D%20re.sub(%22.*--(%5B0-9%2B%5D%2B).*%22%2C%20%22%5C%5C1%22%2C%20url%2C%20count%3D1)%0A%0A%20%20%20%20%20%20%20%20new_url%20%3D%20scheme%20%2B%20%22%3A%2F%2F%22%20%2B%20netloc%0A%0A%20%20%20%20%20%20%20%20if%20buildnumber%20!%3D%20url%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20new_url%20%3D%20new_url%20%2B%20%22%2F%22%20%2B%20buildnumber%20%2B%20%22%2F%22%0A%0A%20%20%20%20%20%20%20%20print(f%22DEBUG%3A%20notebook%20url%20(trimmed)%3A%20%7Bnew_url%7D%22)%0A%0A%20%20%20%20%20%20%20%20await%20micropip.install(%22xdsl%20%40%20%22%20%2B%20new_url%20%2B%20%22%2Fxdsl-0.0.0-py3-none-any.whl%22)%0A%0A%20%20%20%20await%20import_xdsl()%0A%20%20%20%20from%20xdsl.utils%20import%20marimo%20as%20xmo%0A%0A%20%20%20%20return%20(xmo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20from%20xdsl.ir%20import%20Block%2C%20Region%0A%20%20%20%20from%20xdsl.builder%20import%20Builder%2C%20InsertPoint%0A%20%20%20%20from%20xdsl.dialects%20import%20builtin%2C%20riscv%2C%20riscv_cf%2C%20riscv_func%2C%20rv32%0A%20%20%20%20from%20xdsl.printer%20import%20Printer%0A%20%20%20%20from%20xdsl.parser%20import%20Parser%0A%20%20%20%20from%20xdsl.context%20import%20Context%0A%20%20%20%20import%20difflib%0A%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20Block%2C%0A%20%20%20%20%20%20%20%20Builder%2C%0A%20%20%20%20%20%20%20%20Context%2C%0A%20%20%20%20%20%20%20%20InsertPoint%2C%0A%20%20%20%20%20%20%20%20Parser%2C%0A%20%20%20%20%20%20%20%20Printer%2C%0A%20%20%20%20%20%20%20%20builtin%2C%0A%20%20%20%20%20%20%20%20difflib%2C%0A%20%20%20%20%20%20%20%20riscv%2C%0A%20%20%20%20%20%20%20%20riscv_cf%2C%0A%20%20%20%20%20%20%20%20riscv_func%2C%0A%20%20%20%20%20%20%20%20rv32%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20RISC-V%20Dialects%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20RISC-V%0A%0A%20%20%20%20The%20%5BRISC-V%5D(https%3A%2F%2Friscv.org%2F)%20instruction%20set%20is%20a%20small%2C%20extensible%20set%20of%20instructions%20that%20is%20gaining%20in%20popularity%20in%20research%20and%20industry.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.accordion(%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Click%20here%20for%20some%20resources%20on%20the%20RISC-V%20ISA%20and%20assembly%20format%22%3A%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20*%20%5BCheat%20Sheet%5D(https%3A%2F%2Fwww.cl.cam.ac.uk%2Fteaching%2F1617%2FECAD%2BArch%2Ffiles%2Fdocs%2FRISCVGreenCardv8-20151013.pdf)%0A%20%20%20%20*%20%5BAssembly%20Manual%5D(https%3A%2F%2Fgithub.com%2Friscv-non-isa%2Friscv-asm-manual%2Fblob%2Fmain%2Fsrc%2Fasm-manual.adoc)%0A%20%20%20%20*%20%5BISA%20Manual%5D(https%3A%2F%2Fgithub.com%2Friscv%2Friscv-isa-manual)%0A%20%20%20%20*%20%5BDetailed%20Instruction%20Definition%5D(https%3A%2F%2Fmsyksphinz-self.github.io%2Friscv-isadoc%2Fhtml%2Frvi.html)%0A%20%20%20%20*%20%5BABI%5D(https%3A%2F%2Fd3s.mff.cuni.cz%2Ffiles%2Fteaching%2Fnswi200%2F202324%2Fdoc%2Friscv-abi.pdf)%0A%20%20%20%20*%20%5BFormal%20Specification%5D(https%3A%2F%2Fgithub.com%2Friscv%2Fsail-riscv)%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Simple%20Arithmetic%20in%20RISC-V%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Here%20is%20a%20simple%20C%20function%20and%20its%20corresponding%20assembly%3A%0A%0A%20%20%20%20%60%60%60C%0A%20%20%20%20int%20multiply_add(int%20a%2C%20int%20b%2C%20int%20c)%20%7B%0A%20%20%20%20%20%20%20%20return%20a%20%2B%20b%20*%20c%3B%0A%20%20%20%20%7D%0A%20%20%20%20%60%60%60%0A%0A%20%20%20%20%60%60%60asm%0A%20%20%20%20%23%20Label%20corresponding%20to%20the%20function%20name%0A%20%20%20%20%23%20Arguments%20passed%20in%20a0%2C%20a1%2C%20a2%20registers%0A%20%20%20%20%23%20Result%20expected%20to%20be%20stored%20in%20a0%20register%20at%20the%20end%20of%20execution%0A%20%20%20%20multiply_add%3A%0A%20%20%20%20%20%20%20%20%23%20a1%20%3C-%20a2%20*%20a1%0A%20%20%20%20%20%20%20%20mul%20%20%20%20%20a1%2C%20a2%2C%20a1%0A%20%20%20%20%20%20%20%20%23%20a0%20%3C-%20a0%20%2B%20a1%0A%20%20%20%20%20%20%20%20add%20%20%20%20%20a0%2C%20a0%2C%20a1%0A%20%20%20%20%20%20%20%20%23%20Assembly%20pseudo-operation%20that%20jumps%20to%20the%20caller-passed%20return%20address%0A%20%20%20%20%20%20%20%20ret%0A%20%20%20%20%60%60%60%0A%0A%20%20%20%20(%5BCompiler%20Explorer%5D(https%3A%2F%2Fgodbolt.org%2Fz%2Fvscn4n1oh))%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20A%20few%20aspects%20of%20assembly%20make%20it%20difficult%20to%20reason%20about%20directly.%0A%20%20%20%20It%20doesn't%20track%20dependencies%20explicitly%2C%20making%20it%20difficult%20to%20know%20what%20the%20values%20in%20the%20inputs%20of%20an%20operation%20are%2C%20and%20whether%20its%20results%20will%20be%20used.%0A%20%20%20%20Control%20flow%20is%20done%20via%20jumps%20to%20labels%2C%20such%20as%20the%20%60multiply_add%60%20above.%0A%20%20%20%20In%20order%20to%20represent%20and%20reason%20about%20assembly-level%20code%2C%20we%20introduce%20a%20set%20of%20backend%20dialects%3A%20%60riscv%60%2C%20%60riscv_func%60%2C%20and%20%60riscv_cf%60.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20The%20%60riscv%60%20Dialect%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20The%20%60risv%60%20dialect%20contains%20definitions%20for%20static%20information%20and%20operations.%0A%0A%20%20%20%20The%20four%20kinds%20of%20static%20information%20in%20RISC-V%20assembly%20are%20strings%2C%20integers%2C%20labels%2C%20and%20registers.%0A%20%20%20%20The%20%60riscv%60%20dialect%20includes%20integer%20and%20float%20registers%20(%60IntRegisterType%60%20%26%20%60FloatRegisterType%60).%0A%20%20%20%20Both%20of%20these%20register%20classes%20encode%20both%20the%20information%20about%20the%20binary%20encoding%20of%20the%20register%20(e.g.%20%60x0%60%2C%20%60x11%60)%20and%20its%20pretty%20assembly%20name%20(e.g.%20%60zero%60%2C%20%60a1%60).%0A%0A%20%20%20%20The%20pretty%20assembly%20names%20reflect%20the%20RISC-V%20ABI.%20The%20registers%20%60x0%60%20to%20%60x4%60%20are%20specified%20to%20store%20some%20system%20information%3A%20%60zero%60%20for%20a%20register%20that%20always%20has%20the%200%20value%2C%20%60ra%60%20to%20store%20the%20return%20address%20to%20jump%20to%2C%20%60sp%60%20for%20stack%20pointer%2C%20%60gp%60%20for%20global%20pointer%2C%20%60tp%60%20for%20thread%20pointer.%20The%20%60a0-a7%60%20registers%20are%20used%20to%20pass%20function%20arguments%20and%20results.%20The%20%60s0-s11%60%20registers%20are%20expected%20to%20have%20the%20same%20values%20before%20and%20after%20function%20calls.%20The%20%60t0-t6%60%20registers%20are%20temporary%20registers%20that%20are%20not%20expected%20to%20have%20the%20same%20values%20before%20and%20after%20function%20calls.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(riscv)%3A%0A%20%20%20%20%23%20Explictly%20constructing%20registers%0A%0A%20%20%20%20riscv.IntRegisterType.from_name(%22zero%22)%2C%20riscv.IntRegisterType.from_name(%22a1%22)%2C%20riscv.IntRegisterType.from_name(%22s2%22)%2C%20riscv.IntRegisterType.from_name(%22t3%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(riscv)%3A%0A%20%20%20%20%23%20Using%20the%20Registers%20helper%0A%0A%20%20%20%20riscv.Registers.ZERO%2C%20riscv.Registers.A1%2C%20riscv.Registers.S2%2C%20riscv.Registers.T3%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20We%20use%20these%20registers%20as%20the%20types%20of%20the%20operands%20and%20results%20of%20operations%20in%20the%20riscv%20dialect.%0A%20%20%20%20Let's%20construct%20a%20dummy%20block%20with%20some%20operations%20in%20it%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(Block%2C%20Builder%2C%20InsertPoint%2C%20Printer%2C%20riscv)%3A%0A%20%20%20%20block%20%3D%20Block(arg_types%3D(riscv.Registers.A0%2C%20riscv.Registers.A1))%0A%20%20%20%20a0%2C%20a1%20%3D%20block.args%0A%20%20%20%20builder%20%3D%20Builder(InsertPoint.at_end(block))%0A%0A%20%20%20%20%23%20Explicitly%20specify%20result%20registers%0A%20%20%20%20addi_op%20%3D%20builder.insert(riscv.AddiOp(a0%2C%2042%2C%20rd%3Driscv.Registers.A2))%0A%20%20%20%20sub_op%20%3D%20builder.insert(riscv.SubOp(a0%2C%20a1%2C%20rd%3Driscv.Registers.A3))%0A%20%20%20%20mul_op%20%3D%20builder.insert(riscv.MulOp(addi_op.rd%2C%20sub_op.rd%2C%20rd%3Driscv.Registers.A4))%0A%0A%20%20%20%20Printer().print_block(block)%0A%20%20%20%20return%20(block%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Note%20that%20the%20_i_%20in%20the%20%60addi%60%20operation%20above%20stands%20for%20_immediate_%2C%20or%20a%20constant%20value%20in%20the%20assembly.%0A%20%20%20%20These%20can%20be%20integers%20or%20labels%2C%20in%20which%20case%20the%20assembler%20will%20resolve%20the%20immediate%20to%20the%20value%20referred%20to%20by%20the%20label.%0A%0A%20%20%20%20Almost%20all%20the%20operations%20in%20the%20riscv%20dialect%20correspond%20to%20the%20instructions%20in%20the%20RISC-V%20ISA.%0A%20%20%20%20RISC-V%20assembly%20has%20operations%20that%20correspond%201%3A1%20with%20instructions%2C%20as%20well%20as%20pseudo-operations%20that%20are%20syntactic%20sugar%20for%20other%20operations%2C%20such%20as%20the%20%60nop%60%20instruction%20that%20desugars%20to%20%60addi%20x0%2C%20x0%2C%200%60.%0A%0A%20%20%20%20%5BThe%20RISC-V%20Assembly%20Manual%5D(https%3A%2F%2Fgithub.com%2Friscv-non-isa%2Friscv-asm-manual%2Fblob%2Fmain%2Fsrc%2Fasm-manual.adoc%23a-listing-of-standard-risc-v-pseudoinstructions)%20has%20the%20list%20of%20pseudo-instructions%20in%20RISC-V.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Printing%20Assembly%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20All%20operations%20in%20the%20%60riscv%60%20dialect%20implement%20an%20%60assembly_line%60%20function%20that%20communicates%20how%20they%20should%20be%20displayed%20in%20assembly%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(block)%3A%0A%20%20%20%20for%20op%20in%20block.ops%3A%0A%20%20%20%20%20%20%20%20print(op.assembly_line())%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Functions%20and%20the%20%60riscv_func%60%20Dialect%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20When%20compiling%20a%20function%20for%20certain%20hardware%2C%20an%20Application%20Binary%20Interface%20(ABI)%20specifies%20things%20like%20which%20registers%20will%20hold%20the%20function%20arguments%20when%20the%20function%20begins%2C%20which%20registers%20will%20hold%20the%20results%20when%20the%20function%20ends%2C%20which%20registers%20are%20overridden%2C%20etc.%0A%0A%20%20%20%20We%20use%20the%20%60riscv_func%60%20dialect%20to%20represent%20RISC-V-specific%20functions%20that%20encode%20these%20calling%20convention%20considerations%20in%20the%20IR.%0A%0A%20%20%20%20Here%20is%20our%20%60mul%60%20function%20from%20above%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20mul_ir%20%3D%20%22%22%22%0A%20%20%20%20riscv_func.func%20%40mul(%25num%3A%20!riscv.reg%3Ca0%3E)%20-%3E%20!riscv.reg%3Ca0%3E%20%7B%0A%20%20%20%20%20%20%25res%20%3D%20riscv.mul%20%25num%2C%20%25num%20%3A%20(!riscv.reg%3Ca0%3E%2C%20!riscv.reg%3Ca0%3E)%20-%3E%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%20%20riscv_func.return%20%25res%20%3A%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%7D%0A%20%20%20%20%22%22%22%0A%20%20%20%20return%20(mul_ir%2C)%0A%0A%0A%40app.cell%0Adef%20_(Parser%2C%20ctx%2C%20mul_ir%2C%20riscv%2C%20xmo)%3A%0A%20%20%20%20mul_module%20%3D%20Parser(ctx%2C%20mul_ir).parse_module()%0A%0A%20%20%20%20xmo.asm_html(riscv.riscv_code(mul_module))%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Unstructured%20Control%20Flow%20and%20the%20%60riscv_cf%60%20Dialect%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20The%20C%20programming%20language%20allows%20for%20both%20_structured_%20control%20flow%20with%20the%20%60if%60%2C%20%60for%60%2C%20and%20%60while%60%20constructs%2C%20and%20_unstructured_%20flow%20using%20goto.%20The%20two%20functions%20below%20lower%20to%20exactly%20the%20same%20assembly%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%60%60%60C%0A%20%20%20%20int%20switch1(int%20a%2C%20int%20b%2C%20int%20c)%20%7B%0A%20%20%20%20%20%20%20%20if%20(a)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20b%3B%0A%20%20%20%20%20%20%20%20%7D%20else%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20c%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%0A%20%20%20%20int%20switch2(int%20a%2C%20int%20b%2C%20int%20c)%20%7B%0A%20%20%20%20%20%20%20%20if%20(!a)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20goto%20c_label%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20b%3B%0A%20%20%20%20c_label%3A%0A%20%20%20%20%20%20%20%20return%20c%3B%0A%20%20%20%20%7D%0A%20%20%20%20%60%60%60%0A%0A%20%20%20%20(%5BCompiler%20Explorer%5D(https%3A%2F%2Fgodbolt.org%2Fz%2FMzh4ojG3r))%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20At%20the%20assembly%20level%2C%20the%20code%20structure%20looks%20much%20more%20like%20the%20code%20in%20%60switch2%60.%0A%0A%20%20%20%20To%20represent%20jumps%20in%20the%20assembly%2C%20we%20use%20blocks%20and%20successors.%0A%20%20%20%20For%20example%2C%20the%20%5Bbeq%5D(https%3A%2F%2Fmsyksphinz-self.github.io%2Friscv-isadoc%2Fhtml%2Frvi.html%23beq)%20instruction%2C%20which%20jumps%20by%20(or%20_breaks%20to_)%20the%20specified%20offset%20(or%20to%20the%20specified%20label)%20if%20the%20values%20in%20the%20source%20registers%20are%20equal%2C%20is%20represented%20with%20the%20%60riscv.BeqOp%60%20operation%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(Parser%2C%20ctx%2C%20xmo)%3A%0A%20%20%20%20switch_ir%20%3D%20%22%22%22%5C%0A%20%20%20%20riscv_func.func%20%40switch(%25a%3A%20!riscv.reg%3Ca0%3E%2C%20%25b%3A%20!riscv.reg%3Ca1%3E%2C%20%25c%3A%20!riscv.reg%3Ca2%3E)%20-%3E%20!riscv.reg%3Ca0%3E%20%7B%0A%20%20%20%20%20%20%25zero%20%3D%20rv32.get_register%20%3A%20!riscv.reg%3Czero%3E%0A%20%20%20%20%20%20riscv_cf.beq%20%25a%20%3A%20!riscv.reg%3Ca0%3E%2C%20%25zero%20%3A%20!riscv.reg%3Czero%3E%2C%20%5Ebb2()%2C%20%5Ebb1()%0A%20%20%20%20%5Ebb1()%3A%0A%20%20%20%20%20%20%25res_b%20%3D%20riscv.mv%20%25b%20%3A%20(!riscv.reg%3Ca1%3E)%20-%3E%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%20%20riscv_func.return%20%25res_b%20%3A%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%5Ebb2()%3A%0A%20%20%20%20%20%20riscv.label%20%22c_label%22%0A%20%20%20%20%20%20%25res_c%20%3D%20riscv.mv%20%25c%20%3A%20(!riscv.reg%3Ca2%3E)%20-%3E%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%20%20riscv_func.return%20%25res_c%20%3A%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%7D%0A%20%20%20%20%22%22%22%0A%20%20%20%20switch_module%20%3D%20Parser(ctx%2C%20switch_ir).parse_module()%0A%20%20%20%20switch_module.verify()%0A%20%20%20%20xmo.module_html(switch_module)%0A%20%20%20%20return%20(switch_module%2C)%0A%0A%0A%40app.cell%0Adef%20_(riscv%2C%20switch_module)%3A%0A%20%20%20%20%23%20We%20can%20print%20this%20IR%20as%20assembly%0A%20%20%20%20switch_asm%20%3D%20riscv.riscv_code(switch_module)%0A%20%20%20%20print(switch_asm)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Note%20that%20there%20are%20a%20few%20discrepancies%20between%20the%20assembly%20and%20the%20IR.%0A%20%20%20%20While%20in%20the%20IR%20we%20specified%20both%20the%20%22then%22%20and%20the%20%22else%22%20successors%2C%20in%20assembly%20the%20block%20implicitly%20falls%20through.%0A%20%20%20%20We%20represent%20this%20by%20adding%20a%20verification%20method%20to%20the%20jump%20operations%20that%20checks%20that%20the%20%22else%22%20block%20is%20the%20one%20immediately%20following%20the%20conditional%20jump.%0A%20%20%20%20The%20second%20discrepancy%20is%20that%20the%20conditional%20jump%20in%20assembly%20specifies%20the%20label%20to%20jump%20to.%0A%20%20%20%20During%20assembly%20printing%2C%20the%20%60BeqOp%60%20looks%20at%20the%20first%20operation%20in%20the%20block%20and%2C%20if%20it%20finds%20a%20%60LabelOperation%60%2C%20prints%20the%20corresponding%20value.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Exercise%3A%20Fib%20IR%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20fib_text%20%3D%20%22%22%22%5C%0A%20%20%20%20%23%20The%20label%20corresponding%20to%20the%20fib%20function%0A%20%20%20%20fib%3A%0A%20%20%20%20%20%20%20%20bge%20zero%2C%20a0%2C%20.LBB1_4%0A%20%20%20%20%20%20%20%20li%20a2%2C%201%0A%20%20%20%20%20%20%20%20li%20a3%2C%201%0A%20%20%20%20%23%20Label%20inserted%20by%20Clang%20corresponding%20to%20the%20loop%20body%0A%20%20%20%20.LBB1_2%3A%0A%20%20%20%20%20%20%20%20add%20a4%2C%20a2%2C%20a3%0A%20%20%20%20%20%20%20%20addi%20a0%2C%20a0%2C%20-1%0A%20%20%20%20%20%20%20%20mv%20a1%2C%20a3%0A%20%20%20%20%20%20%20%20mv%20a2%2C%20a3%0A%20%20%20%20%20%20%20%20mv%20a3%2C%20a4%0A%20%20%20%20%20%20%20%20%23%20Jump%20to%20beginning%20of%20loop%20body%20if%20need%20to%20do%20more%20work%0A%20%20%20%20%20%20%20%20bne%20zero%2C%20a0%2C%20.LBB1_2%0A%20%20%20%20%20%20%20%20%23%20Moves%20the%20result%20value%20to%20the%20first%20integer%20return%20register%2C%20as%20specified%20by%20ABI%0A%20%20%20%20%20%20%20%20mv%20a0%2C%20a1%0A%20%20%20%20%20%20%20%20ret%0A%20%20%20%20%23%20Label%20inserted%20by%20Clang%20corresponding%20to%20the%20case%20where%20the%20input%20is%20%3C%3D%200%2C%20can%20just%20return%201%0A%20%20%20%20.LBB1_4%3A%0A%20%20%20%20%20%20%20%20li%20a0%2C%201%0A%20%20%20%20%20%20%20%20ret%0A%20%20%20%20%22%22%22%0A%20%20%20%20return%20(fib_text%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20In%20this%20exercise%2C%20we%20will%20rewrite%20the%20following%20function%20to%20assembly-level%20IR%3A%0A%0A%20%20%20%20%60%60%60C%0A%20%20%20%20%2F%2F%20Assume%20n%20non-negative%0A%20%20%20%20int%20fib(int%20n)%20%7B%0A%20%20%20%20%20%20%20%20int%20a%20%3D%201%3B%0A%20%20%20%20%20%20%20%20int%20b%20%3D%201%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20%2B%2Bi)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20c%20%3D%20a%20%2B%20b%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20a%20%3D%20b%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20b%20%3D%20c%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20a%3B%0A%20%20%20%20%7D%0A%20%20%20%20%60%60%60%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(fib_text%2C%20mo)%3A%0A%20%20%20%20mo.md(fr%22%22%22%0A%20%20%20%20This%20is%20the%20expected%20assembly%3A%0A%0A%20%20%20%20%60%60%60asm%0A%20%20%20%20%7Bfib_text%7D%0A%20%20%20%20%60%60%60%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(comment_only_line%2C%20fib_text)%3A%0A%20%20%20%20fib_cleaned%20%3D%20%22%5Cn%22.join(line%20for%20line%20in%20fib_text.splitlines()%20if%20not%20comment_only_line.findall(line))%0A%20%20%20%20return%20(fib_cleaned%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20fib_editor%20%3D%20mo.ui.code_editor(%22%22%22%5C%0A%20%20%20%20riscv_func.func%20%40fib(%25num%3A%20!riscv.reg%3Ca0%3E)%20-%3E%20!riscv.reg%3Ca0%3E%20%7B%0A%20%20%20%20%20%20%25zero%20%3D%20rv32.get_register%20%3A%20!riscv.reg%3Czero%3E%0A%20%20%20%20%20%20riscv_cf.bge%20%25zero%3A%20!riscv.reg%3Czero%3E%2C%20%25num%20%3A!riscv.reg%3Ca0%3E%2C%20%5Ebb4()%2C%20%5Ebb1()%0A%20%20%20%20%5Ebb1()%3A%0A%20%20%20%20%20%20%25a_init%20%3D%20rv32.li%201%20%3A%20!riscv.reg%3Ca2%3E%0A%20%20%20%20%20%20%25b_init%20%3D%20rv32.li%201%20%3A%20!riscv.reg%3Ca3%3E%0A%20%20%20%20%20%20riscv_cf.branch%20%5Ebb2%20(%25num%20%3A%20!riscv.reg%3Ca0%3E%2C%20%25a_init%20%3A%20!riscv.reg%3Ca2%3E%2C%20%25b_init%20%3A%20!riscv.reg%3Ca3%3E)%0A%20%20%20%20%5Ebb2(%25i%3A%20!riscv.reg%3Ca0%3E%2C%20%25a_in%3A%20!riscv.reg%3Ca2%3E%2C%20%25b_in%3A%20!riscv.reg%3Ca3%3E)%3A%0A%20%20%20%20%20%20riscv.label%20%22.LBB1_2%22%0A%20%20%20%20%20%20%25sum%20%3D%20rv32.li%202%20%3A%20!riscv.reg%3Ca4%3E%0A%20%20%20%20%20%20%25i_next%20%3D%20rv32.li%203%20%3A%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%20%20%25temp%20%3D%20rv32.li%204%20%3A%20!riscv.reg%3Ca1%3E%0A%20%20%20%20%20%20%25a_next%20%3D%20rv32.li%205%20%3A%20!riscv.reg%3Ca2%3E%0A%20%20%20%20%20%20%25b_next%20%3D%20rv32.li%206%20%3A%20!riscv.reg%3Ca3%3E%0A%20%20%20%20%20%20riscv_cf.bne%20%25zero%3A%20!riscv.reg%3Czero%3E%2C%20%25i_next%20%3A%20!riscv.reg%3Ca0%3E%2C%20%5Ebb2(%25i_next%20%3A%20!riscv.reg%3Ca0%3E%2C%20%25a_next%20%3A%20!riscv.reg%3Ca2%3E%2C%20%25b_next%20%3A%20!riscv.reg%3Ca3%3E)%2C%20%5Ebb3()%0A%20%20%20%20%5Ebb3()%3A%0A%20%20%20%20%20%20%25res%20%3D%20riscv.mv%20%25temp%20%3A%20(!riscv.reg%3Ca1%3E)%20-%3E%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%20%20riscv_func.return%20%25num%20%3A%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%5Ebb4()%3A%0A%20%20%20%20%20%20riscv.label%20%22.LBB1_4%22%0A%20%20%20%20%20%20%25res_early%20%3D%20rv32.li%201%20%3A%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%20%20riscv_func.return%20%25res_early%20%3A%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%7D%22%22%22%2C%20language%3D%22javascript%22)%0A%20%20%20%20return%20(fib_editor%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(fib_editor%2C%20mo)%3A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20Modify%20the%20following%20IR%20to%20reduce%20the%20diff%20below%3A%0A%0A%20%20%20%20%7Bfib_editor%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(Parser%2C%20ctx%2C%20difflib%2C%20fib_cleaned%2C%20fib_editor%2C%20mo%2C%20riscv)%3A%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20_module%20%3D%20Parser(ctx%2C%20fib_editor.value).parse_module()%0A%20%20%20%20%20%20%20%20_module.verify()%0A%20%20%20%20%20%20%20%20_asm%20%3D%20riscv.riscv_code(_module)%0A%20%20%20%20%20%20%20%20_diff%20%3D%20%22%5Cn%22.join(difflib.ndiff(_asm.splitlines()%2C%20fib_cleaned.splitlines()))%0A%20%20%20%20%20%20%20%20_res%20%3D%20f%22%22%22%0A%20%20%20%20%60%60%60asm%0A%20%20%20%20%7B_diff%7D%0A%20%20%20%20%60%60%60%0A%20%20%20%20%22%22%22%0A%20%20%20%20except%20Exception%20as%20e%3A%0A%20%20%20%20%20%20%20%20_res%20%3D%20f%22%7Btype(e).__name__%7D%3A%20%7Be%7D%22%0A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20Diff%3A%0A%0A%20%20%20%20%7B_res%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20%23%20Solution%0A%0A%20%20%20%20_%20%3D%20%22%22%22%5C%0A%20%20%20%20riscv_func.func%20%40fib(%25num%3A%20!riscv.reg%3Ca0%3E)%20-%3E%20!riscv.reg%3Ca0%3E%20%7B%0A%20%20%20%20%20%20%25zero%20%3D%20rv32.get_register%20%3A%20!riscv.reg%3Czero%3E%0A%20%20%20%20%20%20riscv_cf.bge%20%25zero%3A%20!riscv.reg%3Czero%3E%2C%20%25num%20%3A!riscv.reg%3Ca0%3E%2C%20%5Ebb4()%2C%20%5Ebb1()%0A%20%20%20%20%5Ebb1()%3A%0A%20%20%20%20%20%20%25a_init%20%3D%20rv32.li%201%20%3A%20!riscv.reg%3Ca2%3E%0A%20%20%20%20%20%20%25b_init%20%3D%20rv32.li%201%20%3A%20!riscv.reg%3Ca3%3E%0A%20%20%20%20%20%20riscv_cf.branch%20%5Ebb2%20(%25num%20%3A%20!riscv.reg%3Ca0%3E%2C%20%25a_init%20%3A%20!riscv.reg%3Ca2%3E%2C%20%25b_init%20%3A%20!riscv.reg%3Ca3%3E)%0A%20%20%20%20%5Ebb2(%25i%3A%20!riscv.reg%3Ca0%3E%2C%20%25a_in%3A%20!riscv.reg%3Ca2%3E%2C%20%25b_in%3A%20!riscv.reg%3Ca3%3E)%3A%0A%20%20%20%20%20%20riscv.label%20%22.LBB1_2%22%0A%20%20%20%20%20%20%25sum%20%3D%20riscv.add%20%25a_in%2C%20%25b_in%20%3A%20(!riscv.reg%3Ca2%3E%2C%20!riscv.reg%3Ca3%3E)%20-%3E%20!riscv.reg%3Ca4%3E%0A%20%20%20%20%20%20%25i_next%20%3D%20riscv.addi%20%25i%2C%20-1%20%3A%20(!riscv.reg%3Ca0%3E)%20-%3E%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%20%20%25temp%20%3D%20riscv.mv%20%25b_in%20%3A%20(!riscv.reg%3Ca3%3E)%20-%3E%20!riscv.reg%3Ca1%3E%0A%20%20%20%20%20%20%25a_next%20%3D%20riscv.mv%20%25b_in%20%3A%20(!riscv.reg%3Ca3%3E)%20-%3E%20!riscv.reg%3Ca2%3E%0A%20%20%20%20%20%20%25b_next%20%3D%20riscv.mv%20%25sum%20%3A%20(!riscv.reg%3Ca4%3E)%20-%3E%20!riscv.reg%3Ca3%3E%0A%20%20%20%20%20%20riscv_cf.bne%20%25zero%3A%20!riscv.reg%3Czero%3E%2C%20%25i_next%20%3A%20!riscv.reg%3Ca0%3E%2C%20%5Ebb2(%25i_next%20%3A%20!riscv.reg%3Ca0%3E%2C%20%25a_next%20%3A%20!riscv.reg%3Ca2%3E%2C%20%25b_next%20%3A%20!riscv.reg%3Ca3%3E)%2C%20%5Ebb3()%0A%20%20%20%20%5Ebb3()%3A%0A%20%20%20%20%20%20%25res%20%3D%20riscv.mv%20%25temp%20%3A%20(!riscv.reg%3Ca1%3E)%20-%3E%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%20%20riscv_func.return%20%25num%20%3A%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%5Ebb4()%3A%0A%20%20%20%20%20%20riscv.label%20%22.LBB1_4%22%0A%20%20%20%20%20%20%25res_early%20%3D%20rv32.li%201%20%3A%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%20%20riscv_func.return%20%25res_early%20%3A%20!riscv.reg%3Ca0%3E%0A%20%20%20%20%7D%0A%20%20%20%20%22%22%22%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(Context%2C%20builtin%2C%20riscv%2C%20riscv_cf%2C%20riscv_func%2C%20rv32)%3A%0A%20%20%20%20ctx%20%3D%20Context()%0A%20%20%20%20ctx.load_dialect(builtin.Builtin)%0A%20%20%20%20ctx.load_dialect(riscv.RISCV)%0A%20%20%20%20ctx.load_dialect(riscv_cf.RISCV_Cf)%0A%20%20%20%20ctx.load_dialect(riscv_func.RISCV_Func)%0A%20%20%20%20ctx.load_dialect(rv32.RV32)%0A%20%20%20%20return%20(ctx%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20re%0A%0A%20%20%20%20comment_only_line%20%3D%20re.compile(r%22%5E%5Cs*%23.*%24%22)%0A%20%20%20%20return%20(comment_only_line%2C)%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A