#MilkIR

frontend IR or bytecode
        |
        v
     MilkIR SSA  -- verify and optimize here
        |
        v
    Target VCode -- select instructions directly, then allocate registers

#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

#DFG and layout ownership

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

#Embedding context fields

#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/native or the owning dialect adapter.
5. Add a direct rewrite only when it is locally profitable and preserves the instruction's semantic contract.

#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.optimize_with_level(func, O1)

  inspect(result.changed, content="true")
  inspect(@optimize.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. Stream it into a native target with Milky2018/milkir/native.

#Related packages