Start of live variable analysis

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