#MilkIR

frontend IR or bytecode
        |
        v
     MilkIR SSA  -- verify and optimize here
        |
        v
      MachV IR   -- select instructions and allocate registers later

#Start with one small function

add_one(x: i32) -> i32 = x + 1

///|
test "build add_one" {
  let builder = FunctionBuilder::FunctionBuilder("add_one")

  let x = builder.add_param(I32)
  builder.add_result(I32)

  let one = builder.iconst_i32(1)
  let answer = builder.iadd(x, one)
  builder.return_([answer])

  let func = builder.finalize()
  inspect(func.verify(), content="()")
  inspect(
    func.print(),
    content=(
      #|function add_one(v0:i32) -> i32 {
      #|block0:
      #|    v1:i32 = iconst 1
      #|    v2:i32 = iadd v0, v1
      #|    return v2
      #|}
      #|
    ),
  )
}

function add_one(v0:i32) -> i32 {  function parameter v0 has type i32
block0:                             execution starts in block0
    v1:i32 = iconst 1              create the constant 1
    v2:i32 = iadd v0, v1           add x and 1, producing a new value
    return v2                       return that value
}

#The six concepts to know

1. Create a builder.
2. Declare function parameters and result types.
3. Emit instructions.
4. End the current block with return_, jump, a branch, or trap.
5. Call finalize, then verify the function.

#Opcode families

#Semantic ownership

1. Add its operand and result contract to the verifier.
2. Classify its trap, memory, and observable-effect behavior in the opcode semantic summary.
3. Add its textual representation to the printer.
4. Add its instruction selection to MilkIR-MachV Lowering.
5. Add an e-graph encoding only if the e-graph node language represents it.

#Why values are called SSA values

v0:i32 = ...          old x
v1:i32 = iconst 1
v2:i32 = iadd v0, v1  new x

#Comparisons do not require extra blocks

///|
test "build max_i32 with select" {
  let builder = FunctionBuilder::FunctionBuilder("max_i32")
  let lhs = builder.add_param(I32)
  let rhs = builder.add_param(I32)
  builder.add_result(I32)

  let lhs_is_greater = builder.icmp_sgt(lhs, rhs)
  let result = builder.select(lhs_is_greater, lhs, rhs)
  builder.return_([result])

  let func = builder.finalize()
  inspect(func.verify(), content="()")
  inspect(func.print().contains("icmp.sgt"), content="true")
  inspect(func.print().contains("select"), content="true")
}

#Control flow: blocks and terminators

                 +--------------+
                 |    block0    |
                 | test cond    |
                 +------+-------+
                        |
              +---------+---------+
              |                   |
              v                   v
        +-----------+       +-----------+
        | then_block|       | else_block|
        +-----+-----+       +-----+-----+
              |                   |
              +---------+---------+
                        |
                        v
                 +------------+
                 | join_block |
                 +------------+

#Passing values between blocks

///|
test "pass a value into a join block" {
  let builder = FunctionBuilder::FunctionBuilder("add_if")
  let input = builder.add_param(I32)
  let condition = builder.add_param(I32)
  builder.add_result(I32)

  let add_block = builder.create_block()
  let unchanged_block = builder.create_block()
  let join_block = builder.create_block()
  let result = builder.add_block_param(join_block, I32)

  builder.brnz(condition, add_block, unchanged_block)

  builder.switch_to_block(add_block)
  let one = builder.iconst_i32(1)
  let incremented = builder.iadd(input, one)
  builder.jump(join_block, [incremented])

  builder.switch_to_block(unchanged_block)
  builder.jump(join_block, [input])

  builder.switch_to_block(join_block)
  builder.return_([result])

  let func = builder.finalize()
  inspect(func.verify(), content="()")
  inspect(func.blocks.length(), content="4")
  inspect(func.blocks[3].params.length(), content="1")
}

add_block       --jump [incremented]--+
                                         >-- join_block(result) -- return result
unchanged_block --jump [input]----------+

#Verification

let func = builder.finalize()
func.verify()

• the function contains at least one block;
• each referenced operand has been defined;
• each block has a terminator;
• core instructions have the expected operand arity;
• operands that must agree have matching types;
• comparison results have type I32.

#Optimization

///|
test "fold a constant expression" {
  let builder = FunctionBuilder::FunctionBuilder("constant_answer")
  builder.add_result(I32)
  let ten = builder.iconst_i32(10)
  let twenty = builder.iconst_i32(20)
  let answer = builder.iadd(ten, twenty)
  builder.return_([answer])

  let func = builder.finalize()
  let result = optimize_with_level(func, O1)

  inspect(result.changed, content="true")
  inspect(instruction_count(func), content="1")
  inspect(func.print().contains("iconst 30"), content="true")
  inspect(func.verify(), content="()")
}

#Counted-loop unrolling at O3

#Calls, memory, and traps

#External calls

1. operand 0 is the function pointer;
2. operands 1 and later are ordinary arguments;
3. num_args counts every operand after the callee pointer.

#Traps and effects

#Dialect-specific operations

///|
test "validate a dialect opcode descriptor" {
  let descriptor = ExtOpDescriptor::ExtOpDescriptor("demo", "checked_add", 1)
  let opcode = ExtOp::ExtOp("demo", "checked_add", FixedArray::make(1, 32))

  inspect(opcode.matches_descriptor(descriptor), content="true")
  inspect(descriptor.expected_immediate_count(), content="1")
}

#Typical frontend workflow

1. Map source types to MilkIR Types.
2. Create a FunctionBuilder, then declare the function parameters and results.
3. Translate each source basic block, keeping a map from source values to MilkIR Values.
4. Represent merges and loop-carried values with block parameters and jump arguments.
5. Finalize and verify the function.
6. Optimize it at the desired level.
7. Lower it to the next IR, for example with Milky2018/milkir_machv.

#Related packages