summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPaweł Dybiec <pdybiec@stud.cs.uni.wroc.pl>2019-01-13 12:52:47 +0100
committerPaweł Dybiec <pdybiec@stud.cs.uni.wroc.pl>2019-01-13 12:52:47 +0100
commit66cc1ea68b5d558cb2acd6ea698f20b04d9b43be (patch)
tree606881423bc8bbedd5d7459409e98c714a4f3675
parenta8a49e5b1f968d4ae160052a35242efc7ea30e30 (diff)
Start of live variable analysis
-rw-r--r--source/mod_student/live_variables.ml50
-rw-r--r--source/xi/xi.ml2
-rw-r--r--source/xi_lib/#hardcoded.ml#118
-rw-r--r--source/xi_lib/analysis.ml52
-rw-r--r--source/xi_lib/analysis_domain.ml5
-rw-r--r--xisdk/mod_uwr.cmabin1226060 -> 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