Lir¶
Lir is the low-level intermediate language of AIHC.
The module Aihc.Lir.Lower lowers GC-GRIN to Lir.
Each back end takes Lir as its input.
The code is in bin/aihc/compiler/lir/.
The specification is docs/lir.md.
Properties¶
- Lir is a control-flow graph in static single assignment form.
- A block has parameters. Lir has no phi instructions.
- Each operation has a defined result. An operation that has no valid result traps.
- Lir has no garbage collector and no exception handler. GRIN makes both explicit before the Lir lowering.
- Lir has no hidden state. The runtime registers are declared globals or function parameters.
- The text format and the in-memory representation have the same information. The printer and the parser round-trip each module.
Parts of the runtime system are also written in Lir. Thus, the optimizer can see user code and runtime code as one program.
Names and types¶
| Form | Example | Meaning |
|---|---|---|
%name |
%acc |
A value in a function |
@name |
@aihc_lir_eval |
A symbol: a function, a global, or a data object |
name |
eval_slow_9 |
A block label in a function |
| Type | Meaning |
|---|---|
i1 |
A boolean |
i8, i16, i32, i64 |
An integer with no sign. Each operation gives the sign that it uses. |
f32, f64 |
An IEEE 754 binary float |
ptr |
The address of data |
code |
The address of a function |
Back ends¶
| Target | Back end | Output |
|---|---|---|
apple-arm64 |
Aihc.Arm64.Lir |
Mach-O objects |
linux-amd64 |
Aihc.Amd64.Lir |
ELF objects |
llvm |
Aihc.Llvm.Lir |
Textual LLVM IR |
wasm32-wasip3 |
Aihc.Wasm.Lir |
WebAssembly for WASI P3 |
aihc build --keep-lir writes the Lir of each module to <Module>.o.lir beside its object.
Example¶
This module has a recursive function on lists:
module Example where
append :: [a] -> [a] -> [a]
append [] ys = ys
append (x : xs) ys = x : append xs ys
The compiler makes this Lir program for the module:
extern func @aihc_heap_collect_replay(ptr, i64, i64, ptr, ptr, i64) -> i64 cc c
extern func @aihc_lir_continue_p(ptr, ptr, ptr, ptr, ptr)
extern func @aihc_lir_eval(ptr, ptr, ptr, ptr, ptr)
extern func @aihc_lir_resume(ptr, ptr)
extern func @aihc_replay_suspend(ptr, ptr) -> ptr cc c
extern func @aihc_stack_grow(ptr, ptr, i64, ptr) -> ptr cc c
extern data @aihc_c_aihc__mprim_GHC__dTypes___k__j_0
extern data @aihc_c_aihc__mprim_GHC__dTypes___o_0
extern data @aihc_lir_cps_update_info
export func @aihc_f__Example___sappend__sp__up__sp(%hp_0: ptr, %sp_1: ptr, %base_2: ptr, %x_3: ptr, %y_4: ptr, %$cps_return_5: ptr) {
entry:
jump eval_check_6(%x_3)
eval_check_6(%current_9: ptr):
%header_word_10 = load.dependent i64 [%current_9] region heap
%info_word_11 = and i64 %header_word_10, -4
%header_12 = ptr.from_int %info_word_11
%needs_eval_13 = load.invariant i8 [%header_12 + 44] align 1
%needs_eval_14 = zext i8 %needs_eval_13 to i64
%not_value_15 = ne i64 %needs_eval_14, 0
br %not_value_15, eval_not_value_16, eval_ready_7
cold eval_not_value_16:
%indirection_20 = eq i64 %needs_eval_14, 2
br %indirection_20, eval_follow_17, eval_thunk_18
cold eval_thunk_18:
%tag_21 = and i64 %header_word_10, 3
%claimed_22 = eq i64 %tag_21, 1
br %claimed_22, eval_owner_19, eval_slow_8
cold eval_owner_19:
%word_23 = load.dependent ptr [%current_9 + 8] region heap
%header_word_24 = load.dependent i64 [%word_23] region heap
%info_word_25 = and i64 %header_word_24, -4
%header_26 = ptr.from_int %info_word_25
%word_kind_27 = load.invariant i8 [%header_26 + 43] align 1
%word_kind_28 = zext i8 %word_kind_27 to i64
%thread_29 = eq i64 %word_kind_28, 7
%queue_30 = eq i64 %word_kind_28, 15
%owned_31 = or i1 %thread_29, %queue_30
br %owned_31, eval_slow_8, eval_check_6(%word_23)
cold eval_follow_17:
%next_32 = load.dependent ptr [%current_9 + 8] region heap
jump eval_check_6(%next_32)
eval_ready_7:
tailcall @aihc_f__Example___sappend__sp__up__sp__ucont(%hp_0, %sp_1, %base_2, %$cps_return_5, %y_4, %current_9)
eval_slow_8:
%tag_37 = and i64 %header_word_10, 1
%unclaimed_38 = eq i64 %tag_37, 0
br %unclaimed_38, force_thunk_33, force_helper_36
force_thunk_33:
%kind_39 = load.invariant i8 [%header_12 + 43] align 1
%kind_40 = zext i8 %kind_39 to i64
%thunk_41 = eq i64 %kind_40, 2
br %thunk_41, force_stack_34, force_helper_36
force_stack_34:
%sp_42 = ptr.add %sp_1, 48
%sp_limit_43 = load ptr [%base_2 + 88] align 1 word
%stack_fits_44 = le.u ptr %sp_42, %sp_limit_43
%hp_limit_45 = load ptr [%base_2 + 24] align 1 word
%heap_fits_46 = le.u ptr %hp_0, %hp_limit_45
%fits_47 = and i1 %stack_fits_44, %heap_fits_46
br %fits_47, force_enter_35, force_helper_36
cold force_helper_36:
tailcall @aihc_lir_force_pp(%hp_0, %sp_1, %base_2, %current_9, @aihc_lir_info_2, %$cps_return_5, %y_4)
force_enter_35:
store ptr @aihc_lir_info_2, [%sp_1] align 8 region stack
store ptr %$cps_return_5, [%sp_1 + 8] align 8 region stack
store ptr %y_4, [%sp_1 + 16] align 8 region stack
%update_48 = ptr.add %sp_1, 24
store ptr @aihc_lir_cps_update_info, [%update_48] align 8 region stack
store ptr %sp_1, [%update_48 + 8] align 8 region stack
store ptr %current_9, [%update_48 + 16] align 8 region stack
%entry_49 = load.invariant code [%header_12 + 24] align 1 word
tailcall.indirect %entry_49(%hp_0, %sp_42, %base_2, %current_9, %update_48) : (ptr, ptr, ptr, ptr, ptr)
}
data @aihc_lir_bitmap_0 align 1 = { bytes "\x00\x01\x01\x01" }
data @aihc_f__Example___sappend__sp__up__sp__ucont_ri align 8 = { code @aihc_f__Example___sappend__sp__up__sp__ucont, ptr @aihc_lir_bitmap_0, ptr null, code @aihc_lir_replay_entry_ppp, ptr null, i8 4, i8 1, i8 0, i8 1, i8 0, i8 0, i16 0 }
func @aihc_f__Example___sappend__sp__up__sp__ucont(%hp_50: ptr, %sp_51: ptr, %base_52: ptr, %$cps_return_53: ptr, %y_54: ptr, %case_value_55: ptr) {
entry:
%roots_56 = stack.alloc 24 align 8
%hp_limit_57 = load ptr [%base_52 + 24] align 1 word
%heap_end_58 = ptr.add %hp_50, 56
%heap_fits_59 = le.u ptr %heap_end_58, %hp_limit_57
br %heap_fits_59, gc_reserved_61(%$cps_return_53, %case_value_55, %y_54, %hp_50), gc_collect_60
cold gc_collect_60:
tailcall @aihc_lir_collect_replay_ppp(%hp_50, %sp_51, %base_52, %$cps_return_53, %y_54, %case_value_55, @aihc_f__Example___sappend__sp__up__sp__ucont_ri, 7)
gc_reserved_61(%$cps_return$gc_62: ptr, %case_value$gc_63: ptr, %y$gc_64: ptr, %hp_65: ptr):
%header_word_68 = load i64 [%case_value$gc_63] align 8 region heap
%info_word_69 = and i64 %header_word_68, -4
%header_70 = ptr.from_int %info_word_69
%matches_71 = eq ptr %header_70, @aihc_c_aihc__mprim_GHC__dTypes___k__j_0
br %matches_71, alt_66, alt_67
alt_66:
tailcall @aihc_lir_eval(%hp_65, %sp_51, %base_52, %y$gc_64, %$cps_return$gc_62)
alt_67:
%x_72 = load ptr [%case_value$gc_63 + 8] align 8 region heap
%xs_73 = load ptr [%case_value$gc_63 + 16] align 8 region heap
%hp_74 = ptr.add %hp_65, 32
store ptr @aihc_lir_info_3, [%hp_65] align 8 region heap
store ptr %xs_73, [%hp_65 + 16] align 8 region heap
store ptr %y$gc_64, [%hp_65 + 24] align 8 region heap
%hp_75 = ptr.add %hp_74, 24
store ptr @aihc_c_aihc__mprim_GHC__dTypes___o_0, [%hp_74] align 8 region heap
store ptr %x_72, [%hp_74 + 8] align 8 region heap
store ptr %hp_65, [%hp_74 + 16] align 8 region heap
%header_word_76 = load i64 [%$cps_return$gc_62] align 8 region stack
%info_word_77 = and i64 %header_word_76, -4
%header_78 = ptr.from_int %info_word_77
%entry_79 = load.invariant code [%header_78 + 24] align 1 word
%forward_82 = eq code %entry_79, null
br %forward_82, continue_slow_80, continue_enter_81
cold continue_slow_80:
tailcall @aihc_lir_continue_p(%hp_75, %sp_51, %base_52, %$cps_return$gc_62, %hp_74)
continue_enter_81:
tailcall.indirect %entry_79(%hp_75, %$cps_return$gc_62, %base_52, %$cps_return$gc_62, %hp_74) : (ptr, ptr, ptr, ptr, ptr)
}
export data mut @_Example_append align 8 = { ptr @aihc_lir_info_0 }
data @aihc_lir_bitmap_1 align 1 = { bytes "\x01\x01" }
func @aihc_lir_info_0_e(%hp_83: ptr, %sp_84: ptr, %base_85: ptr, %object_86: ptr, %continuation_87: ptr, %supplied_88: ptr, %supplied_89: ptr) {
entry:
tailcall @aihc_f__Example___sappend__sp__up__sp(%hp_83, %sp_84, %base_85, %supplied_88, %supplied_89, %continuation_87)
}
data @aihc_lir_info_0 align 8 = { code @aihc_f__Example___sappend__sp__up__sp, ptr @aihc_lir_bitmap_1, ptr @aihc_lir_info_1, code @aihc_lir_info_0_e, ptr null, i8 0, i8 2, i8 0, i8 1, i8 0, i8 1, i16 0 }
func @aihc_lir_info_1_e(%hp_90: ptr, %sp_91: ptr, %base_92: ptr, %object_93: ptr, %continuation_94: ptr, %supplied_95: ptr) {
entry:
%stored_96 = load ptr [%object_93 + 8] align 8
tailcall @aihc_f__Example___sappend__sp__up__sp(%hp_90, %sp_91, %base_92, %stored_96, %supplied_95, %continuation_94)
}
data @aihc_lir_info_1 align 8 = { code @aihc_f__Example___sappend__sp__up__sp, ptr @aihc_lir_bitmap_1, ptr null, code @aihc_lir_info_1_e, ptr null, i8 1, i8 1, i8 0, i8 1, i8 0, i8 2, i16 0 }
data @aihc_lir_bitmap_2 align 1 = { bytes "\x01\x01\x01" }
func @aihc_lir_info_2_e(%hp_97: ptr, %sp_98: ptr, %base_99: ptr, %object_100: ptr, %supplied_102: ptr) {
entry:
%stored_103 = load ptr [%object_100 + 8] align 8
%stored_104 = load ptr [%object_100 + 16] align 8
tailcall @aihc_f__Example___sappend__sp__up__sp__ucont(%hp_97, %sp_98, %base_99, %stored_103, %stored_104, %supplied_102)
}
data @aihc_lir_info_2 align 8 = { code @aihc_f__Example___sappend__sp__up__sp__ucont, ptr @aihc_lir_bitmap_2, ptr null, code @aihc_lir_info_2_e, ptr null, i8 2, i8 1, i8 1, i8 1, i8 0, i8 3, i16 0 }
data @aihc_lir_bitmap_3 align 1 = { bytes "\x00\x01\x01" }
func @aihc_lir_info_3_e(%hp_105: ptr, %sp_106: ptr, %base_107: ptr, %object_108: ptr, %continuation_109: ptr) {
entry:
%stored_110 = load ptr [%object_108 + 16] align 8
%stored_111 = load ptr [%object_108 + 24] align 8
tailcall @aihc_f__Example___sappend__sp__up__sp(%hp_105, %sp_106, %base_107, %stored_110, %stored_111, %continuation_109)
}
data @aihc_lir_info_3 align 8 = { code @aihc_f__Example___sappend__sp__up__sp, ptr @aihc_lir_bitmap_3, ptr null, code @aihc_lir_info_3_e, ptr null, i8 3, i8 0, i8 0, i8 2, i8 1, i8 4, i16 0 }
func @aihc_lir_collect_replay_ppp(%hp_112: ptr, %sp_113: ptr, %base_114: ptr, %value_115: ptr, %value_116: ptr, %value_117: ptr, %info_118: ptr, %words_119: i64) {
entry:
%code_120 = load.invariant code [%info_118] align 1 word
%srt_121 = load.invariant ptr [%info_118 + 32] align 1 word
%roots_122 = stack.alloc 24 align 8
store ptr %value_115, [%roots_122] align 8
store ptr %value_116, [%roots_122 + 8] align 8
store ptr %value_117, [%roots_122 + 16] align 8
store ptr %hp_112, [%base_114 + 16] align 1 word
store ptr %sp_113, [%base_114 + 32] align 1 word
%result_123 = call @aihc_heap_collect_replay(%base_114, %words_119, 3, %roots_122, %srt_121, 5)
%value_124 = load ptr [%roots_122] align 8
%value_125 = load ptr [%roots_122 + 8] align 8
%value_126 = load ptr [%roots_122 + 16] align 8
%hp_127 = load ptr [%base_114 + 16] align 1 word
%suspended_128 = ne i64 %result_123, 0
br %suspended_128, suspend_129, enter_130
cold suspend_129:
store ptr %info_118, [%hp_127] align 8 region heap
store i64 -1, [%hp_127 + 8] align 8 region heap
store ptr %value_124, [%hp_127 + 16] align 8 region heap
store ptr %value_125, [%hp_127 + 24] align 8 region heap
store ptr %value_126, [%hp_127 + 32] align 8 region heap
%hp_131 = ptr.add %hp_127, 40
store ptr %hp_131, [%base_114 + 16] align 1 word
store ptr %sp_113, [%base_114 + 32] align 1 word
%result_132 = call @aihc_replay_suspend(%base_114, %hp_127)
tailcall @aihc_lir_resume(%base_114, %result_132)
enter_130:
tailcall.indirect %code_120(%hp_127, %sp_113, %base_114, %value_124, %value_125, %value_126) : (ptr, ptr, ptr, ptr, ptr, ptr)
}
func @aihc_lir_replay_entry_ppp(%hp_133: ptr, %sp_134: ptr, %base_135: ptr, %closure_136: ptr, %continuation_137: ptr) {
entry:
%index_138 = load i64 [%closure_136 + 8] align 8 region heap
%argument_139 = load ptr [%closure_136 + 16] align 8 region heap
%is_continuation_140 = eq i64 %index_138, 0
%argument_141 = select ptr %is_continuation_140, %continuation_137, %argument_139
%argument_142 = load ptr [%closure_136 + 24] align 8 region heap
%is_continuation_143 = eq i64 %index_138, 1
%argument_144 = select ptr %is_continuation_143, %continuation_137, %argument_142
%argument_145 = load ptr [%closure_136 + 32] align 8 region heap
%is_continuation_146 = eq i64 %index_138, 2
%argument_147 = select ptr %is_continuation_146, %continuation_137, %argument_145
%header_word_148 = load i64 [%closure_136] align 8 region heap
%info_word_149 = and i64 %header_word_148, -4
%header_150 = ptr.from_int %info_word_149
%code_151 = load.invariant code [%header_150] align 1 word
tailcall.indirect %code_151(%hp_133, %sp_134, %base_135, %argument_141, %argument_144, %argument_147) : (ptr, ptr, ptr, ptr, ptr, ptr)
}
func @aihc_lir_force_pp(%hp_152: ptr, %sp_153: ptr, %base_154: ptr, %value_155: ptr, %info_156: ptr, %field_157: ptr, %field_158: ptr) {
entry:
%sp_159 = ptr.add %sp_153, 24
%sp_limit_160 = load ptr [%base_154 + 88] align 1 word
%stack_fits_161 = le.u ptr %sp_159, %sp_limit_160
br %stack_fits_161, stack_pushed_163(%sp_153, %sp_159, %field_157), stack_grow_162
cold stack_grow_162:
store ptr %hp_152, [%base_154 + 16] align 1 word
%result_164 = call @aihc_stack_grow(%base_154, %sp_153, 3, %field_157)
%sp_165 = ptr.add %result_164, 24
%parent_166 = ptr.add %result_164, -16
jump stack_pushed_163(%result_164, %sp_165, %parent_166)
stack_pushed_163(%frame_167: ptr, %sp_168: ptr, %parent_169: ptr):
store ptr %info_156, [%frame_167] align 8 region stack
store ptr %parent_169, [%frame_167 + 8] align 8 region stack
store ptr %field_158, [%frame_167 + 16] align 8 region stack
tailcall @aihc_lir_eval(%hp_152, %sp_168, %base_154, %value_155, %frame_167)
}
The compiler made these programs at the default optimization level. The Lir is for the target linux-amd64.
The page Examples shows more programs.