diff options
| -rw-r--r-- | source/mod_student/live_variables.ml | 50 | ||||
| -rw-r--r-- | source/xi/xi.ml | 2 | ||||
| -rw-r--r-- | source/xi_lib/#hardcoded.ml# | 118 | ||||
| -rw-r--r-- | source/xi_lib/analysis.ml | 52 | ||||
| -rw-r--r-- | source/xi_lib/analysis_domain.ml | 5 | ||||
| -rw-r--r-- | xisdk/mod_uwr.cma | bin | 1226060 -> 1227185 bytes |
6 files changed, 218 insertions, 9 deletions
diff --git a/source/mod_student/live_variables.ml b/source/mod_student/live_variables.ml new file mode 100644 index 0000000..580892b --- /dev/null +++ b/source/mod_student/live_variables.ml @@ -0,0 +1,50 @@ +open Xi_lib +open Iface +open Ir +open Ir_utils +open Analysis (* <--- tu mogą być pomocne komentarze *) +open Analysis_domain + +module Make() = struct + + module Implementation(M:sig val cfg: ControlFlowGraph.t end) = struct + open M + + (* + * Zwróćmy tablicę gdzie każdy wierzchołek jest zainicjalizowany na + * konstruktor Simple (typ BlockKnowledge) gdzie na wejściu/wyjściu + * bloku mamy pusty zbiór rejestrów. + * + * Wierzchołki oznaczające basic-bloki powinny ostatecznie być opisane + * konstruktorem Complex, ale początkowo dla wygody możemy ustawić je na Simple. + * Ważne aby funkcja przeliczająca wiedzę dla bloku podstawowego ostatecznie + * opisał blok za pomocą konstruktora Complex. + *) + let initialize_table () = + let table = Hashtbl.create 513 in + let kw = Knowledge.make ~pre:RegSet.empty ~post:RegSet.empty in + let blk_kw = BlockKnowledge.make_simple kw in + let set v = + Hashtbl.replace table v blk_kw + in + List.iter set @@ ControlFlowGraph.labels cfg; + table + + + let result : LiveVariables.table = initialize_table () + + let rec compute_fixpoint () = + failwith "Not yet implemented" + + let analyse () = + compute_fixpoint (); + result + + end + + let analyse cfg = + let module Instance = Implementation(struct let cfg = cfg end) in + Instance.analyse () + + +end diff --git a/source/xi/xi.ml b/source/xi/xi.ml index aca4997..b064be6 100644 --- a/source/xi/xi.ml +++ b/source/xi/xi.ml @@ -72,7 +72,7 @@ module CommandLine = struct let cmd = let doc = "Compile Xi Program" in - let version = "pracownia4.1-0-ge52fd94" in + let version = "pracownia5-0-geed1995" in Term.(const compile $ xi_log $ extra_debug $ mod_uwr $ plugin $ reg_descr $ stop_after $ output $ source_file), Term.info "xi" ~doc ~version diff --git a/source/xi_lib/#hardcoded.ml# b/source/xi_lib/#hardcoded.ml# new file mode 100644 index 0000000..1c24418 --- /dev/null +++ b/source/xi_lib/#hardcoded.ml# @@ -0,0 +1,118 @@ +xopen Ir + +let word_size = Int32.of_int 4 +let i32_0 = Int32.of_int 0 +let i32_1 = Int32.of_int 1 +let expr_0 = E_Int i32_0 + +let preamble = String.concat "\n" + [ ".data" + ; "endline: .asciiz \"\\n\"" + ; "endmessage: .asciiz \"Exit code: \"" + ; "" + ; ".text" + ; ".set noat" + ; "" + ; "main:" + ; " add $sp, $sp, -4" + ; " sw $ra, 4($sp)" + ; " jal _I_main__i" + ; " move $a1, $v0" + + ; " la $a0, endmessage" + ; " li $v0, 4" + ; " syscall" + + ; " li $v0, 1" + ; " move $a0, $a1" + ; " syscall" + + ; " la $a0, endline" + ; " li $v0, 4" + ; " syscall" + + ; " lw $ra, 4($sp)" + ; " add $sp, $sp, 4" + ; " jr $ra" + ; "" + ; "_xi_concat:" + ; " # t0 = lhs" + ; " # t1 = rhs" + ; " move $t0, $a0" + ; " move $t1, $a1" + ; " # t2 = len(lhs)" + ; " # t3 = len(rhs)" + ; " lw $t2, -4($t0)" + ; " lw $t3, -4($t1)" + ; " # t4 = len(lhs) + len(rhs)" + ; " addu $t4, $t2, $t3" + ; " # v0 = malloc(4*t4+4) " + ; " li $t5, 4" + ; " mul $a0, $t4, $t5" + ; " addiu $a0, $a0, 4" + ; " li $v0, 9" + ; " syscall" + ; " addiu $v0, $v0, 4" + ; " sw $t4, -4($v0)" + ; " move $v1, $v0" + ; " XL0:" + ; " beq $zero, $t2, XL1" + ; " lw $t4, 0($t0)" + ; " sw $t4, 0($v1)" + ; " addiu $t2, $t2, -1" + ; " addiu $t0, $t0, 4" + ; " addiu $v1, $v1, 4" + ; " j XL0" + ; " XL1:" + ; " beq $zero, $t3, XL2" + ; " lw $t4, 0($t1)" + ; " sw $t4, 0($v1)" + ; " addiu $t3, $t3, -1" + ; " addiu $t1, $t1, 4" + ; " addiu $v1, $v1, 4" + ; " j XL1" + ; " XL2:" + ; " jr $ra" + ; "" + ; "_xi_alloc:" + ; " li $v0, 9" + ; " syscall" + ; " jr $ra" + ; "" + ; "_I_printString_ai_:" + ; " # t0 = len a0" + ; " move $t1, $a0" + ; " lw $t0, -4($t1)" + ; " mul $a0, $t0, 4" + ; " addiu $a0, $a0, 2" + ; " li $v0, 9" + ; " syscall" + ; " move $a0, $v0" + ; " move $v1, $v0" + ; " XL10:" + ; " beq $zero, $t0, XL11" + ; " lw $t2, 0($t1)" + ; " sb $t2, 0($v1)" + ; " addiu $t0, $t0, -1" + ; " addu $t1, $t1, 4" + ; " addu $v1, $v1, 1" + ; " j XL10" + ; " XL11:" + ; " li $t0, 10" + ; " sb $t0, 0($v1)" + ; " sb $zero, 1($v1)" + ; " li $v0, 4" + ; " syscall" + ; " jr $ra" + ; "" + ; "" + ; "_I_printInt_i_:" + ; " li $v0, 1" + ; " syscall" + ; " li $v0, 4" + ; " la $a0, endline" + ; " syscall" + ; " jr $ra" + ; "" + ; "" + ] diff --git a/source/xi_lib/analysis.ml b/source/xi_lib/analysis.ml index ac15cb5..f83d400 100644 --- a/source/xi_lib/analysis.ml +++ b/source/xi_lib/analysis.ml @@ -1,10 +1,14 @@ +(* Wiedza dla jakiegoś punktu (instrukcji, bloku, terminatora) *) module Knowledge = struct + (* wierdza na wejściu (pre) oraz wyjściu (post)*) type 'a t = { pre: 'a ; post: 'a } + (* akcesory *) + let pre t = t.pre let post t = t.post @@ -20,14 +24,28 @@ module Knowledge = struct in t - let make pre post : 'a t = {pre; post} + (* konstruktor *) + + let make ~pre ~post : 'a t = {pre; post} + + (* alias *) type 'a table = (Ir.label, 'a t) Hashtbl.t end +(* Wiedza o wierzcholku w grafie sterowania *) module BlockKnowledge = struct + (* + * Simple - mamy tylko wiedzę na wejściu/wyjściu + * - używane w analizach co nie interesują się instrukcjami (jak analiza dominacji) + * lub przy wyszczególnioncyh wierzchołkach entry/exit. + * Complex - mamy wiedzę o instrukcjach wewnątrz bloku + * - block - wiedza na wejściu wyjściu do bloku + * - body - lista instrukcji bloku wraz z wiedzą + * - terminator - terminator bloku wraz z wiedzą + *) type 'a t = | Simple of 'a Knowledge.t | Complex of @@ -36,32 +54,38 @@ module BlockKnowledge = struct ; terminator: 'a Knowledge.t * Ir.terminator } + (* akcesory *) + + (* zwraca wiedzę Knowledge dla całego bloku + * - działa z dwoma konstruktorami *) let block = function | Simple t -> t | Complex {block; _} -> block + + (* zwracają pola pre/post z wiedzy dla całego bloku + * - działa z dwoma konstruktorami *) + let pre t = Knowledge.pre @@ block t let post t = Knowledge.post @@ block t + (* zwraca terminator i wiedzę na jego temat, działa tylko z Complex *) let terminator = function | Simple _ -> failwith "BlockKnowledge.terminator" | Complex t-> t.terminator + (* zwraca listę instrukcji wraz z wiedzą na ich temat, działa tylko z Complex *) let body = function | Simple _ -> failwith "BlockKnowledge.body" | Complex t -> t.body + (* zwraca terminator, działa tylko z Complex *) let terminator_instr t = snd @@ terminator t + (* zwraca wiedzę o terminatorze, działa tylko z Complex *) let terminator_kw t = fst @@ terminator t - let make_complex ~block ~body ~terminator = - Complex { block; body; terminator } - - let make_simple t = Simple t - - type 'a table = (Ir.label, 'a t) Hashtbl.t - + (* setter wiedzy o całym bloku, działa z dwoma konstruktorami *) let alter_prepost ?pre ?post = function | Simple t -> Simple (Knowledge.alter ?pre ?post t) @@ -74,4 +98,16 @@ module BlockKnowledge = struct | Complex _ -> true | Simple _ -> false + (* konstruktory *) + + let make_complex ~block ~body ~terminator = + Complex { block; body; terminator } + + let make_simple t = Simple t + + (* alias *) + + type 'a table = (Ir.label, 'a t) Hashtbl.t + + end diff --git a/source/xi_lib/analysis_domain.ml b/source/xi_lib/analysis_domain.ml index db124e0..420f509 100644 --- a/source/xi_lib/analysis_domain.ml +++ b/source/xi_lib/analysis_domain.ml @@ -75,12 +75,17 @@ end module LiveVariables = struct + (* Dziedzina - zbiór rejestrów *) type domain = Ir.RegSet.t + (* Tablica reprezentująca wynik analizy + * table odwzorowuje etykietkę (Ir.label) na wiedzę o bloku (BlockKnowledge.t) + * *) type table = domain Analysis.BlockKnowledge.table type block_knowledge = domain Analysis.BlockKnowledge.t + (* Pomocnicza funkcja do drukowania zbioru rejestrów *) let string_of_domain x = Ir_utils.string_of_reglist @@ List.of_seq @@ Ir.RegSet.to_seq x end diff --git a/xisdk/mod_uwr.cma b/xisdk/mod_uwr.cma index f59d91f..00ea6d7 100644 --- a/xisdk/mod_uwr.cma +++ b/xisdk/mod_uwr.cma Binary files differ |