eqsat

import%20marimo%0A%0A__generated_with%20%3D%20%220.17.8%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%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%20%20%20%20return%20(xmo%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%20%23%20Embedding%20Equality%20Saturation%20in%20IR%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%20This%20notebook%20presents%20the%20%60equivalence%60%20dialect%20with%20examples.%0A%20%20%20%20The%20%60equivalence%60%20dialect%20refers%20to%20%5Be-graph%5D(https%3A%2F%2Fegraphs-good.github.io%2F)%2C%20a%20graph%20representation%20of%20multiple%20functionally%20equivalent%20programs.%0A%0A%20%20%20%20Here%20is%20an%20MLIR%20module%20with%20an%20input%20function%20and%20three%20rewrites%20lowered%20to%20the%20%5Bpdl_interp%20dialect%5D(https%3A%2F%2Fmlir.llvm.org%2Fdocs%2FDialects%2FPDLInterpOps%2F)%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(ctx%2C%20input_module_string%2C%20xmo)%3A%0A%20%20%20%20from%20xdsl.parser%20import%20Parser%0A%20%20%20%20from%20xdsl.utils.lexer%20import%20Input%0A%0A%20%20%20%20input_module%20%3D%20Parser(ctx%2C%20input_module_string).parse_module()%0A%0A%20%20%20%20xmo.module_html(input_module)%0A%20%20%20%20return%20Parser%2C%20input_module%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%20start%20by%20adding%20e-class%20ops%2C%20which%20represent%20a%20union%20of%20multiple%20ways%20of%20calculating%20the%20same%20value%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(ctx%2C%20input_module%2C%20xmo)%3A%0A%20%20%20%20from%20xdsl.transforms.eqsat_create_eclasses%20import%20EqsatCreateEclassesPass%0A%0A%20%20%20%20_%2C%20eclass_module%20%3D%20EqsatCreateEclassesPass().apply_to_clone(ctx%2C%20input_module)%0A%0A%20%20%20%20xmo.module_html(eclass_module)%0A%20%20%20%20return%20(eclass_module%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%20We%20then%20execute%20the%20%60apply-pdl-interp-eqsat%60%20pass%2C%20which%20applies%20the%20rewrites%20non-destructively.%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%20eclass_module%2C%20pdl_interp_module_string%2C%20xmo)%3A%0A%20%20%20%20from%20xdsl.transforms.apply_eqsat_pdl_interp%20import%20apply_eqsat_pdl_interp%0A%0A%20%20%20%20saturated_module%20%3D%20eclass_module.clone()%0A%20%20%20%20pdl_interp_module%20%3D%20Parser(ctx%2C%20pdl_interp_module_string).parse_module()%0A%0A%20%20%20%20apply_eqsat_pdl_interp(saturated_module%2C%20ctx%2C%20pdl_interp_module)%0A%0A%20%20%20%20xmo.module_html(saturated_module)%0A%20%20%20%20return%20(saturated_module%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%20We%20then%20add%20the%20costs.%20For%20now%20we%20give%20each%20operation%20a%20cost%20of%20%601%60.%20This%20means%20the%20program%20with%20the%20lowest%20cost%20will%20be%20the%20program%20with%20the%20least%20amount%20of%20operations.%20Each%20e-class%20now%20also%20gets%20a%20%60min_cost_index%60%20attribute%2C%20referring%20to%20the%20value%20in%20its%20operand%20list%20with%20the%20lowest%20cost%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(ctx%2C%20saturated_module%2C%20xmo)%3A%0A%20%20%20%20from%20xdsl.transforms.eqsat_add_costs%20import%20EqsatAddCostsPass%0A%0A%20%20%20%20_%2C%20cost_module%20%3D%20EqsatAddCostsPass(default%3D1).apply_to_clone(ctx%2C%20saturated_module)%0A%0A%20%20%20%20xmo.module_html(cost_module)%0A%20%20%20%20return%20(cost_module%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%20And%20then%20we%20extract%20to%20get%20the%20optimal%20result%3A%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(cost_module%2C%20ctx%2C%20xmo)%3A%0A%20%20%20%20from%20xdsl.transforms.eqsat_extract%20import%20EqsatExtractPass%0A%0A%20%20%20%20_%2C%20extracted_module%20%3D%20EqsatExtractPass().apply_to_clone(ctx%2C%20cost_module)%0A%0A%20%20%20%20xmo.module_html(extracted_module)%0A%20%20%20%20return%20(extracted_module%2C)%0A%0A%0A%40app.cell%0Adef%20_(extracted_module)%3A%0A%20%20%20%20def%20test_no_eclass()%3A%0A%20%20%20%20%20%20%20%20from%20xdsl.dialects.equivalence%20import%20ClassOp%0A%20%20%20%20%20%20%20%20%22Test%20that%20the%20extracted%20module%20doesn't%20contain%20e-class%20ops%22%0A%20%20%20%20%20%20%20%20eclass_ops%20%3D%20tuple(op%20for%20op%20in%20extracted_module.walk()%20if%20isinstance(op%2C%20ClassOp))%0A%20%20%20%20%20%20%20%20assert%20not%20eclass_ops%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20input_module_string%20%3D%20%22%22%22%0A%20%20%20%20func.func%20%40impl(%25a%20%3A%20i32)%20-%3E%20i32%20%7B%0A%20%20%20%20%20%20%25two%20%20%20%3D%20arith.constant%202%20%20%3A%20i32%0A%20%20%20%20%20%20%25mul%20%20%20%3D%20arith.muli%20%25a%2C%20%25two%20%3A%20i32%0A%20%20%20%20%20%20%25div%20%20%20%3D%20arith.divui%20%25mul%2C%20%25two%20%3A%20i32%0A%20%20%20%20%20%20func.return%20%25div%20%3A%20i32%0A%20%20%20%20%7D%0A%20%20%20%20%22%22%22%0A%0A%20%20%20%20pdl_interp_module_string%20%3D%20%22%22%22%0A%0A%20%20%20%20pdl_interp.func%20%40matcher(%25arg0%3A%20!pdl.operation)%20%7B%0A%20%20%20%20%20%20%250%20%3D%20eqsat_pdl_interp.get_result%200%20of%20%25arg0%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%250%20%3A%20!pdl.value%20-%3E%20%5Ebb2%2C%20%5Ebb1%0A%20%20%20%20%5Ebb1%3A%20%20%2F%2F%2021%20preds%3A%20%5Ebb0%2C%20%5Ebb2%2C%20%5Ebb3%2C%20%5Ebb4%2C%20%5Ebb5%2C%20%5Ebb7%2C%20%5Ebb8%2C%20%5Ebb19%2C%20%5Ebb20%2C%20%5Ebb21%2C%20%5Ebb22%2C%20%5Ebb23%2C%20%5Ebb24%2C%20%5Ebb25%2C%20%5Ebb26%2C%20%5Ebb27%2C%20%5Ebb28%2C%20%5Ebb29%2C%20%5Ebb30%2C%20%5Ebb31%2C%20%5Ebb32%0A%20%20%20%20%20%20eqsat_pdl_interp.finalize%0A%20%20%20%20%5Ebb2%3A%20%20%2F%2F%20pred%3A%20%5Ebb0%0A%20%20%20%20%20%20%2F%2F%20%22pdl_interp.switch_operation_name%22(%25arg0)%5B%5Ebb1%2C%20%5Ebb3%2C%20%5Ebb19%5D%20%3C%7BcaseValues%20%3D%20%5B%22arith.divui%22%2C%20%22arith.muli%22%5D%7D%3E%20%3A%20(!pdl.operation)%20-%3E%20()%0A%20%20%20%20%20%20pdl_interp.switch_operation_name%20of%20%25arg0%20to%20%5B%22arith.divui%22%2C%20%22arith.muli%22%5D(%5Ebb3%2C%20%5Ebb19)%20-%3E%20%5Ebb1%0A%20%20%20%20%5Ebb3%3A%20%20%2F%2F%20pred%3A%20%5Ebb2%0A%20%20%20%20%20%20pdl_interp.check_operand_count%20of%20%25arg0%20is%202%20-%3E%20%5Ebb4%2C%20%5Ebb1%0A%20%20%20%20%5Ebb4%3A%20%20%2F%2F%20pred%3A%20%5Ebb3%0A%20%20%20%20%20%20pdl_interp.check_result_count%20of%20%25arg0%20is%201%20-%3E%20%5Ebb5%2C%20%5Ebb1%0A%20%20%20%20%5Ebb5%3A%20%20%2F%2F%20pred%3A%20%5Ebb4%0A%20%20%20%20%20%20%251%20%3D%20pdl_interp.get_operand%200%20of%20%25arg0%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%251%20%3A%20!pdl.value%20-%3E%20%5Ebb6%2C%20%5Ebb1%0A%20%20%20%20%5Ebb6%3A%20%20%2F%2F%20pred%3A%20%5Ebb5%0A%20%20%20%20%20%20%252%20%3D%20pdl_interp.get_operand%201%20of%20%25arg0%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%252%20%3A%20!pdl.value%20-%3E%20%5Ebb9%2C%20%5Ebb7%0A%20%20%20%20%5Ebb7%3A%20%20%2F%2F%2011%20preds%3A%20%5Ebb6%2C%20%5Ebb9%2C%20%5Ebb10%2C%20%5Ebb11%2C%20%5Ebb12%2C%20%5Ebb13%2C%20%5Ebb14%2C%20%5Ebb15%2C%20%5Ebb16%2C%20%5Ebb17%2C%20%5Ebb18%0A%20%20%20%20%20%20%253%20%3D%20pdl_interp.get_operand%201%20of%20%25arg0%0A%20%20%20%20%20%20pdl_interp.are_equal%20%251%2C%20%253%20%3A%20!pdl.value%20-%3E%20%5Ebb8%2C%20%5Ebb1%0A%20%20%20%20%5Ebb8%3A%20%20%2F%2F%20pred%3A%20%5Ebb7%0A%20%20%20%20%20%20%254%20%3D%20pdl_interp.get_value_type%20of%20%250%20%3A%20!pdl.type%0A%20%20%20%20%20%20eqsat_pdl_interp.record_match%20%40rewriters%3A%3A%40pdl_generated_rewriter(%254%2C%20%25arg0%20%3A%20!pdl.type%2C%20!pdl.operation)%20%3A%20benefit(1)%2C%20generatedOps(%5B%22arith.constant%22%5D)%2C%20loc(%5B%25arg0%5D)%2C%20root(%22arith.divui%22)%20-%3E%20%5Ebb1%0A%20%20%20%20%5Ebb9%3A%20%20%2F%2F%20pred%3A%20%5Ebb6%0A%20%20%20%20%20%20%255%20%3D%20eqsat_pdl_interp.get_defining_op%20of%20%251%20%3A%20!pdl.value%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%255%20%3A%20!pdl.operation%20-%3E%20%5Ebb10%2C%20%5Ebb7%0A%20%20%20%20%5Ebb10%3A%20%20%2F%2F%20pred%3A%20%5Ebb9%0A%20%20%20%20%20%20pdl_interp.check_operation_name%20of%20%255%20is%20%22arith.muli%22%20-%3E%20%5Ebb11%2C%20%5Ebb7%0A%20%20%20%20%5Ebb11%3A%20%20%2F%2F%20pred%3A%20%5Ebb10%0A%20%20%20%20%20%20pdl_interp.check_operand_count%20of%20%255%20is%202%20-%3E%20%5Ebb12%2C%20%5Ebb7%0A%20%20%20%20%5Ebb12%3A%20%20%2F%2F%20pred%3A%20%5Ebb11%0A%20%20%20%20%20%20pdl_interp.check_result_count%20of%20%255%20is%201%20-%3E%20%5Ebb13%2C%20%5Ebb7%0A%20%20%20%20%5Ebb13%3A%20%20%2F%2F%20pred%3A%20%5Ebb12%0A%20%20%20%20%20%20%256%20%3D%20pdl_interp.get_operand%200%20of%20%255%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%256%20%3A%20!pdl.value%20-%3E%20%5Ebb14%2C%20%5Ebb7%0A%20%20%20%20%5Ebb14%3A%20%20%2F%2F%20pred%3A%20%5Ebb13%0A%20%20%20%20%20%20%257%20%3D%20pdl_interp.get_operand%201%20of%20%255%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%257%20%3A%20!pdl.value%20-%3E%20%5Ebb15%2C%20%5Ebb7%0A%20%20%20%20%5Ebb15%3A%20%20%2F%2F%20pred%3A%20%5Ebb14%0A%20%20%20%20%20%20%258%20%3D%20eqsat_pdl_interp.get_result%200%20of%20%255%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%258%20%3A%20!pdl.value%20-%3E%20%5Ebb16%2C%20%5Ebb7%0A%20%20%20%20%5Ebb16%3A%20%20%2F%2F%20pred%3A%20%5Ebb15%0A%20%20%20%20%20%20pdl_interp.are_equal%20%258%2C%20%251%20%3A%20!pdl.value%20-%3E%20%5Ebb17%2C%20%5Ebb7%0A%20%20%20%20%5Ebb17%3A%20%20%2F%2F%20pred%3A%20%5Ebb16%0A%20%20%20%20%20%20%259%20%3D%20pdl_interp.get_value_type%20of%20%258%20%3A%20!pdl.type%0A%20%20%20%20%20%20%2510%20%3D%20pdl_interp.get_value_type%20of%20%250%20%3A%20!pdl.type%0A%20%20%20%20%20%20pdl_interp.are_equal%20%259%2C%20%2510%20%3A%20!pdl.type%20-%3E%20%5Ebb18%2C%20%5Ebb7%0A%20%20%20%20%5Ebb18%3A%20%20%2F%2F%20pred%3A%20%5Ebb17%0A%20%20%20%20%20%20eqsat_pdl_interp.record_match%20%40rewriters%3A%3A%40pdl_generated_rewriter_0(%257%2C%20%252%2C%20%259%2C%20%256%2C%20%25arg0%20%3A%20!pdl.value%2C%20!pdl.value%2C%20!pdl.type%2C%20!pdl.value%2C%20!pdl.operation)%20%3A%20benefit(1)%2C%20generatedOps(%5B%22arith.divui%22%2C%20%22arith.muli%22%5D)%2C%20loc(%5B%25arg0%2C%20%255%5D)%2C%20root(%22arith.divui%22)%20-%3E%20%5Ebb7%0A%20%20%20%20%5Ebb19%3A%20%20%2F%2F%20pred%3A%20%5Ebb2%0A%20%20%20%20%20%20pdl_interp.check_operand_count%20of%20%25arg0%20is%202%20-%3E%20%5Ebb20%2C%20%5Ebb1%0A%20%20%20%20%5Ebb20%3A%20%20%2F%2F%20pred%3A%20%5Ebb19%0A%20%20%20%20%20%20pdl_interp.check_result_count%20of%20%25arg0%20is%201%20-%3E%20%5Ebb21%2C%20%5Ebb1%0A%20%20%20%20%5Ebb21%3A%20%20%2F%2F%20pred%3A%20%5Ebb20%0A%20%20%20%20%20%20%2511%20%3D%20pdl_interp.get_operand%200%20of%20%25arg0%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%2511%20%3A%20!pdl.value%20-%3E%20%5Ebb22%2C%20%5Ebb1%0A%20%20%20%20%5Ebb22%3A%20%20%2F%2F%20pred%3A%20%5Ebb21%0A%20%20%20%20%20%20%2512%20%3D%20pdl_interp.get_operand%201%20of%20%25arg0%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%2512%20%3A%20!pdl.value%20-%3E%20%5Ebb23%2C%20%5Ebb1%0A%20%20%20%20%5Ebb23%3A%20%20%2F%2F%20pred%3A%20%5Ebb22%0A%20%20%20%20%20%20%2513%20%3D%20eqsat_pdl_interp.get_defining_op%20of%20%2512%20%3A%20!pdl.value%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%2513%20%3A%20!pdl.operation%20-%3E%20%5Ebb24%2C%20%5Ebb1%0A%20%20%20%20%5Ebb24%3A%20%20%2F%2F%20pred%3A%20%5Ebb23%0A%20%20%20%20%20%20pdl_interp.check_operation_name%20of%20%2513%20is%20%22arith.constant%22%20-%3E%20%5Ebb25%2C%20%5Ebb1%0A%20%20%20%20%5Ebb25%3A%20%20%2F%2F%20pred%3A%20%5Ebb24%0A%20%20%20%20%20%20pdl_interp.check_operand_count%20of%20%2513%20is%200%20-%3E%20%5Ebb26%2C%20%5Ebb1%0A%20%20%20%20%5Ebb26%3A%20%20%2F%2F%20pred%3A%20%5Ebb25%0A%20%20%20%20%20%20pdl_interp.check_result_count%20of%20%2513%20is%201%20-%3E%20%5Ebb27%2C%20%5Ebb1%0A%20%20%20%20%5Ebb27%3A%20%20%2F%2F%20pred%3A%20%5Ebb26%0A%20%20%20%20%20%20%2514%20%3D%20pdl_interp.get_attribute%20%22value%22%20of%20%2513%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%2514%20%3A%20!pdl.attribute%20-%3E%20%5Ebb28%2C%20%5Ebb1%0A%20%20%20%20%5Ebb28%3A%20%20%2F%2F%20pred%3A%20%5Ebb27%0A%20%20%20%20%20%20pdl_interp.check_attribute%20%2514%20is%201%20%3A%20i32%20-%3E%20%5Ebb29%2C%20%5Ebb1%0A%20%20%20%20%5Ebb29%3A%20%20%2F%2F%20pred%3A%20%5Ebb28%0A%20%20%20%20%20%20%2515%20%3D%20eqsat_pdl_interp.get_result%200%20of%20%2513%0A%20%20%20%20%20%20pdl_interp.is_not_null%20%2515%20%3A%20!pdl.value%20-%3E%20%5Ebb30%2C%20%5Ebb1%0A%20%20%20%20%5Ebb30%3A%20%20%2F%2F%20pred%3A%20%5Ebb29%0A%20%20%20%20%20%20pdl_interp.are_equal%20%2515%2C%20%2512%20%3A%20!pdl.value%20-%3E%20%5Ebb31%2C%20%5Ebb1%0A%20%20%20%20%5Ebb31%3A%20%20%2F%2F%20pred%3A%20%5Ebb30%0A%20%20%20%20%20%20%2516%20%3D%20pdl_interp.get_value_type%20of%20%2515%20%3A%20!pdl.type%0A%20%20%20%20%20%20%2517%20%3D%20pdl_interp.get_value_type%20of%20%250%20%3A%20!pdl.type%0A%20%20%20%20%20%20pdl_interp.are_equal%20%2516%2C%20%2517%20%3A%20!pdl.type%20-%3E%20%5Ebb32%2C%20%5Ebb1%0A%20%20%20%20%5Ebb32%3A%20%20%2F%2F%20pred%3A%20%5Ebb31%0A%20%20%20%20%20%20eqsat_pdl_interp.record_match%20%40rewriters%3A%3A%40pdl_generated_rewriter_1(%2511%2C%20%25arg0%20%3A%20!pdl.value%2C%20!pdl.operation)%20%3A%20benefit(1)%2C%20loc(%5B%25arg0%2C%20%2513%5D)%2C%20root(%22arith.muli%22)%20-%3E%20%5Ebb1%0A%20%20%20%20%7D%0A%20%20%20%20module%20%40rewriters%20%7B%0A%20%20%20%20%20%20pdl_interp.func%20%40pdl_generated_rewriter(%25arg0%3A%20!pdl.type%2C%20%25arg1%3A%20!pdl.operation)%20%7B%0A%20%20%20%20%20%20%20%20%250%20%3D%20pdl_interp.create_attribute%201%20%3A%20i32%0A%20%20%20%20%20%20%20%20%251%20%3D%20eqsat_pdl_interp.create_operation%20%22arith.constant%22%20%7B%22value%22%20%3D%20%250%7D%20%20-%3E%20(%25arg0%20%3A%20!pdl.type)%0A%20%20%20%20%20%20%20%20%252%20%3D%20eqsat_pdl_interp.get_results%20of%20%251%20%3A%20!pdl.range%3Cvalue%3E%0A%20%20%20%20%20%20%20%20eqsat_pdl_interp.replace%20%25arg1%20with%20(%252%20%3A%20!pdl.range%3Cvalue%3E)%0A%20%20%20%20%20%20%20%20eqsat_pdl_interp.finalize%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20pdl_interp.func%20%40pdl_generated_rewriter_0(%25arg0%3A%20!pdl.value%2C%20%25arg1%3A%20!pdl.value%2C%20%25arg2%3A%20!pdl.type%2C%20%25arg3%3A%20!pdl.value%2C%20%25arg4%3A%20!pdl.operation)%20%7B%0A%20%20%20%20%20%20%20%20%250%20%3D%20eqsat_pdl_interp.create_operation%20%22arith.divui%22(%25arg0%2C%20%25arg1%20%3A%20!pdl.value%2C%20!pdl.value)%20%20-%3E%20(%25arg2%20%3A%20!pdl.type)%0A%20%20%20%20%20%20%20%20%251%20%3D%20eqsat_pdl_interp.get_result%200%20of%20%250%0A%20%20%20%20%20%20%20%20%252%20%3D%20eqsat_pdl_interp.create_operation%20%22arith.muli%22(%25arg3%2C%20%251%20%3A%20!pdl.value%2C%20!pdl.value)%20%20-%3E%20(%25arg2%20%3A%20!pdl.type)%0A%20%20%20%20%20%20%20%20%253%20%3D%20eqsat_pdl_interp.get_result%200%20of%20%252%0A%20%20%20%20%20%20%20%20%254%20%3D%20eqsat_pdl_interp.get_results%20of%20%252%20%3A%20!pdl.range%3Cvalue%3E%0A%20%20%20%20%20%20%20%20eqsat_pdl_interp.replace%20%25arg4%20with%20(%254%20%3A%20!pdl.range%3Cvalue%3E)%0A%20%20%20%20%20%20%20%20eqsat_pdl_interp.finalize%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20pdl_interp.func%20%40pdl_generated_rewriter_1(%25arg0%3A%20!pdl.value%2C%20%25arg1%3A%20!pdl.operation)%20%7B%0A%20%20%20%20%20%20%20%20eqsat_pdl_interp.replace%20%25arg1%20with%20(%25arg0%20%3A%20!pdl.value)%0A%20%20%20%20%20%20%20%20eqsat_pdl_interp.finalize%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%22%22%22%0A%20%20%20%20return%20input_module_string%2C%20pdl_interp_module_string%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20from%20xdsl.context%20import%20Context%0A%20%20%20%20from%20xdsl.dialects%20import%20get_all_dialects%0A%0A%20%20%20%20ctx%20%3D%20Context()%0A%20%20%20%20for%20name%2C%20func%20in%20get_all_dialects().items()%3A%0A%20%20%20%20%20%20%20%20ctx.register_dialect(name%2C%20func)%0A%20%20%20%20return%20(ctx%2C)%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A