From 9fefd626fd6cc312e45b89e4c26dc10a028a4f40 Mon Sep 17 00:00:00 2001 From: Shinya Sato Date: Sun, 27 Feb 2022 22:37:01 +0900 Subject: v0.8.0 --- Changelog.md | 110 ++++- README.md | 112 +++-- comparison/Inpla/main.sh | 4 +- comparison/Inpla/sptestInpla.sh | 3 +- pic/benchmark_reuse_v0.7.3.png | Bin 29840 -> 0 bytes pic/benchmark_reuse_v0.8.0.png | Bin 0 -> 29747 bytes pic/flexibily_expandable.png | Bin 0 -> 26483 bytes src/.#-emacsFibRvc | 1 + src/.#-emacsGvT7Q7 | 1 + src/.#-emacsd3nZKL | 1 + src/id_table.h | 6 +- src/inpla.y | 1018 +++++++++++++++++++++++++++++---------- 12 files changed, 949 insertions(+), 307 deletions(-) delete mode 100644 pic/benchmark_reuse_v0.7.3.png create mode 100644 pic/benchmark_reuse_v0.8.0.png create mode 100644 pic/flexibily_expandable.png create mode 100644 src/.#-emacsFibRvc create mode 100644 src/.#-emacsGvT7Q7 create mode 100644 src/.#-emacsd3nZKL diff --git a/Changelog.md b/Changelog.md index 07c156c..b64b6ae 100644 --- a/Changelog.md +++ b/Changelog.md @@ -1,21 +1,49 @@ # Change log -### v0.7.3-1 (released on 24 February 2022) +### v0.8.0 (released on 27 February 2022) -#### Bug Fix: -* **TRO Bytecode Optimisation for empty connection sequences**: The optimisation for empty connection sequence had caused Segmentation fault, and it was fixed. -* **Bytecode instruction execution**: The following error were fixed. - * Execution of an instruction of TRO for general agents: Indirection was not correctly applied. - * Execution of an instruction for substitutions of global names: `pc++` was applied to a macro argument, and it caused some increments. +| | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla7 | Inpla7_r | +| ------------ | :------: | :------: | :----: | :----: | :------: | :----: | :------: | +| ack(3,11) | 2.31 | **0.41** | - | 4.42 | 3.53 | 0.88 | 0.75 | +| fib 38 | 1.60 | **0.26** | 8.49 | 2.30 | 2.83 | 0.42 | 0.46 | +| bsort 40000 | 34.81 | 11.17 | 76.72 | 17.64 | 16.92 | 2.75 | **2.70** | +| isort 40000 | **0.02** | 2.97 | 36.63 | 6.72 | 8.34 | 1.20 | 1.34 | +| qsort 800000 | **0.15** | 1.16 | 97.30 | 6.07 | 1.81 | 0.64 | 0.37 | +| msort 800000 | 0.46 | 1.00 | 98.27 | 3.92 | 1.36 | 0.46 | **0.35** | + +#### New Features: + +* **Flexibly expandable ring buffer for agents and names**: We can change the size of buffers that are inserted when all of nodes run up, though it was fixed before. It is possible to start a small heap for small computation, and it can be expanded for larger computation. + + ![speedup-ratio](pic/flexibily_expandable.png) + + * To set the initial size to 2^*n*, use the execution option `-Xms n` (default `n` is 12, so the size is 4096): + * To set the increasing magnification to 2^*n*, use the option `-Xmt n` (default `n` is 3, so the inserted heap is 8 times of the run up heap) + + To use the fixed sized ring buffer, comment out the following definition in `src/inpla.y`: + + ``` + #define EXPANDABLE_HEAP // Expandable heaps for agents and names + ``` ### v0.7.3 (released on 20 February 2022) -#### New Features: -* **Bytecode optimisation inspired by Tail Recursive Optimisation**: As a result this optimisation brings about faster computation up to about twice in comparison with no reuse-annotated computation. +| | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla7 | Inpla7_r | +| ------------ | :------: | :------: | :----: | :----: | :------: | :----: | :------: | +| ack(3,11) | 2.31 | **0.41** | - | 4.75 | 3.47 | 1.49 | 0.73 | +| fib 38 | 1.60 | **0.26** | 8.49 | 2.39 | 2.89 | 0.48 | 0.51 | +| bsort 40000 | 34.81 | 11.17 | 76.72 | 15.56 | 17.16 | 3.99 | **2.81** | +| isort 40000 | **0.02** | 2.97 | 36.63 | 7.66 | 8.38 | 2.01 | 1.38 | +| qsort 800000 | **0.15** | 1.16 | 97.30 | 2.32 | 1.82 | 0.56 | 0.36 | +| msort 800000 | 0.46 | 1.00 | 98.27 | 1.23 | 1.37 | 0.42 | **0.33** | + +#### Polished: - * When interaction rules have a connection whose the left and the right hand sides have the same IDs to the active pair, computation of the connection can be realised by a loop operation that applies the same bytecode sequence of the rule with replacing ports of active pairs. For instance, take the following Fibonacci number: +* **Bytecode optimisation inspired by Tail Recursive Optimisation**: As a result, this optimisation brings about faster computation up to about twice in comparison with no reuse-annotated computation. + + * When an interaction rule has a connection whose both sides agents have the same IDs to the active pair, computation of the connection can be realised by applying the same bytecode sequence of the rule to the connection after replacing ports of the active pair into agents ports of the connection. Moreover, when the connection is placed at the tail of a connection sequence, we can restart the same bytecode sequence after replacing these ports. For instance, take the following rule for Fibonacci number: ``` fib(ret) >< (int n) @@ -23,14 +51,14 @@ | n == 1 => ret~1 | _ => Add(ret, cnt2)~cnt1, fib(cnt1)~(n-1), fib(cnt2)~(n-2); ``` - This rule has `fib(cnt2)~(n-2)` as the connection for the loop, and it is possible to be applied the same bytecode sequence of `fib(ret)><(int n)` with replacing these ports `ret`, `n` into `cnt2`, `n-2`, respectively. So, this rule computation is realised by execution of the other connections and the loop operation for the connection `fib(cnt2)~(n-2)`. + This rule has a connection `fib(cnt2)~(n-2)` at the tail of the third connection sequence. The connection is computable by using the same bytecode sequence of `fib(ret)><(int n)` with replacing these ports `ret`, `n` into `cnt2`, `n-2`, respectively. So, the computation of the third connection sequence is realised by bytecode sequences of the other connections and the port replacing, and a loop operation to start execution from the top of the rule sequence. * This is also possible not only for agents like `(int n)`, but also other constructor agents such as `Cons(x,xs)`, `S(x)`. The following is a part of rules for insertion sort: ``` isort(ret) >< x:xs => insert(ret, x)~cnt, isort(cnt)~xs; ``` - When the `xs` connects to an `Cons(y,ys)` agent, then the computation is also realised by the loop operation because the `isort(cnt)~xs` can be regarded as `isort(cnt)~y:ys`, whose agents have the same IDs of the active pair. So, by introducing a conditional branch if the `xs` is connected to a `Cons` agent or not, this rule computation is also realised by the loop operation. + When the `xs` connects to an `Cons(y,ys)` agent, then the computation is also realised by the loop operation because the `isort(cnt)~xs` can be regarded as `isort(cnt)~y:ys`, whose agents have the same IDs of the active pair. So, by introducing a conditional branch whether the `xs` connects to a `Cons` agent or not, this rule computation is also realised by the loop operation. * In this version, this optimisation will be triggered when such the connection is placed at the tail of a sequence of connections. @@ -54,7 +82,17 @@ ### v0.7.1 (released on 4 February 2022) +| | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla7 | Inpla7_r | +| ------------ | :------: | :------: | :----: | :----: | :------: | :----: | :------: | +| ack(3,11) | 2.31 | **0.41** | - | 4.78 | 3.55 | 1.51 | 0.74 | +| fib 38 | 1.60 | **0.26** | 8.49 | 3.10 | 2.95 | 0.60 | 0.50 | +| bsort 40000 | 34.81 | 11.17 | 76.72 | 24.85 | 18.22 | 7.39 | **2.92** | +| isort 40000 | **0.02** | 2.97 | 36.63 | 11.85 | 8.71 | 3.65 | 1.41 | +| qsort 800000 | **0.15** | 1.16 | 97.30 | 3.54 | 1.88 | 0.83 | 0.34 | +| msort 800000 | 0.46 | 1.00 | 98.27 | 2.26 | 1.32 | 0.60 | **0.33** | + #### Polished: + * **Bytecodes**: Bytecodes of virtual machines are expressed by three address codes ordered as `op dest src1 src2`. The order is changed to the ordinary one `op src1 src2 dest`. * **Bytecode optimisation**: The following is introduced: @@ -68,7 +106,17 @@ ### v0.7.0 (released on 30 January 2022) +| | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla7 | Inpla7_r | +| ------------ | :------: | :------: | :----: | :----: | :------: | :----: | :------: | +| ack(3,11) | 2.31 | **0.41** | - | 5.22 | 3.86 | 1.52 | 0.81 | +| fib 38 | 1.60 | **0.26** | 8.49 | 3.52 | 3.31 | 0.62 | 0.55 | +| bsort 40000 | 34.81 | 11.17 | 76.72 | 25.76 | 18.21 | 7.36 | **2.87** | +| isort 40000 | **0.02** | 2.97 | 36.63 | 11.97 | 8.62 | 3.64 | 1.44 | +| qsort 800000 | **0.15** | 1.16 | 97.30 | 3.55 | 1.87 | 0.82 | 0.35 | +| msort 800000 | 0.46 | 1.00 | 98.27 | 2.29 | 1.34 | 0.60 | **0.33** | + #### New Features: + * **Logical operators on integers**: Not `!` (`not`), And `&&` (`and`) and Or `||` (`or`) are available. Only `0` is regarded as False and these operators return `1` for Truth, `0` for False. * **Bytecode optimisations**: Bytecodes are optimised by Copy propagation, Dead code elimination methods. In addition, Register0 is used to store comparison results, and conditional branches are performed according to the value of Register0. To prevent those optimisation, comment out the following definition `OPTIMISE_IMCODE` in `src/inpla.y`: @@ -80,7 +128,17 @@ ### v0.6.2 (released on 20 January 2022) +| | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla7 | Inpla7_r | +| ------------ | :------: | :------: | :----: | :----: | :------: | :----: | :------: | +| ack(3,11) | 2.31 | **0.41** | - | 5.46 | 4.16 | 1.56 | 0.86 | +| fib 38 | 1.60 | **0.26** | 8.49 | 3.93 | 3.68 | 0.69 | 0.62 | +| bsort 40000 | 34.81 | 11.17 | 76.72 | 25.75 | 19.06 | 7.32 | **3.14** | +| isort 40000 | **0.02** | 2.97 | 36.63 | 12.38 | 9.25 | 3.64 | 1.53 | +| qsort 800000 | **0.15** | 1.16 | 97.30 | 3.83 | 1.91 | 0.77 | 0.35 | +| msort 800000 | 0.46 | 1.00 | 98.27 | 2.39 | 1.39 | 0.69 | **0.41** | + #### New Features: + * **Retaining the big ring buffer**: The new expandable buffer for agents and names require extra costs sometimes, so the old one, that is the big ring buffer, is embedded into programs sources. Comment out the following definition `EXPANDABLE_HEAP` in `src/inpla.y` when the old one is needed: ``` @@ -103,7 +161,17 @@ ### v0.6.0 (released on 9 January 2022) +| | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla7 | Inpla7_r | +| ------------ | :------: | :------: | :----: | :----: | :------: | :----: | :------: | +| ack(3,11) | 2.31 | **0.41** | - | 5.54 | 4.57 | 1.58 | 0.92 | +| fib 38 | 1.60 | **0.26** | 8.49 | 3.96 | 3.83 | 0.67 | 0.62 | +| bsort 40000 | 34.81 | 11.17 | 76.72 | 26.31 | 21.07 | 7.39 | **3.41** | +| isort 40000 | **0.02** | 2.97 | 36.63 | 12.59 | 10.03 | 3.65 | 1.63 | +| qsort 800000 | **0.15** | 1.16 | 97.30 | 3.79 | 2.04 | 0.77 | 0.37 | +| msort 800000 | 0.46 | 1.00 | 98.27 | 2.50 | 1.45 | 0.64 | **0.39** | + #### New Features: + * **Introduced new data structure for ring buffers for agents and names**: The ring buffers are automatically expanded when all elements of these are used up. Each size starts from 2^18 (=262144), and it will be twice, triple and so on automatically. To adjust the unit size, change the following definition in `src/inpla.y`: ``` @@ -115,7 +183,17 @@ ### v0.5.6 (released on 6 January 2022) +| | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla7 | Inpla7_r | +| ------------ | :------: | :------: | :----: | :----: | :------: | :----: | :------: | +| ack(3,11) | 2.31 | **0.41** | - | 4.89 | 4.45 | 0.97 | 0.90 | +| fib 38 | 1.60 | **0.26** | 8.49 | 3.74 | 3.70 | 0.57 | 0.56 | +| bsort 40000 | 34.81 | 11.17 | 76.72 | 25.74 | 19.82 | 6.39 | **3.07** | +| isort 40000 | **0.02** | 2.97 | 36.63 | 12.41 | 9.37 | 3.04 | 1.49 | +| qsort 800000 | **0.15** | 1.16 | 97.30 | 2.02 | 1.63 | 0.75 | 0.40 | +| msort 800000 | 0.46 | 1.00 | 98.27 | 1.29 | 1.28 | 0.65 | **0.43** | + #### Bug Fix: + * The index of the ring buffer for agents had not been correctly initialised. It was fixed the same as the way of the ring buffer for names. @@ -206,7 +284,17 @@ ### v0.4.2 (released on 16 October 2021) +| | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla7 | Inpla7_r | +| ------------ | :------: | :------: | :----: | :----: | :------: | :----: | :------: | +| ack(3,11) | 2.31 | **0.41** | - | 4.76 | 4.36 | 0.98 | 0.88 | +| fib 38 | 1.60 | **0.26** | 8.49 | 3.59 | 3.56 | 0.56 | 0.54 | +| bsort 40000 | 34.81 | 11.17 | 76.72 | 22.85 | 18.40 | 5.53 | **2.94** | +| isort 40000 | **0.02** | 2.97 | 36.63 | 10.59 | 8.74 | 2.59 | 1.43 | +| qsort 800000 | **0.15** | 1.16 | 97.30 | 1.85 | 1.55 | 0.76 | 0.41 | +| msort 800000 | **0.46** | 1.00 | 98.27 | 1.18 | 1.34 | 0.65 | 0.49 | + #### Improved: + * Line edit was improved to support multi-line paste, according to the following suggestion: https://github.com/antirez/linenoise/issues/43 * History in Line edit becomes available. diff --git a/README.md b/README.md index 41ae73d..872cdf4 100644 --- a/README.md +++ b/README.md @@ -6,18 +6,18 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you write programs for sequential execution, it works also in multi-threaded parallel execution. Each thread is managed on each CPU-core with POSIX-thread library. -* The current version is 0.7.3-1 (BugFix) released on **24 February 2022**. (See [Changelog.md](Changelog.md) for details.) +* The current version is 0.8.0 released on **27 February 2022**. (See [Changelog.md](Changelog.md) for details.) -![speedup-ratio](pic/benchmark_reuse_v0.7.3.png) +![speedup-ratio](pic/benchmark_reuse_v0.8.0.png) | | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla8 | Inpla8_r | | -------------- | :------: | :------: | :----: | :----: | :------: | :----: | :------: | -| ack(3,11) | 2.31 | **0.41** | - | 4.75 | 3.47 | 1.53 | 0.69 | -| fib 38 | 1.60 | **0.26** | 8.49 | 2.39 | 2.89 | 0.48 | 0.47 | -| bsort 40000 | 34.81 | 11.17 | 76.72 | 15.56 | 17.16 | 3.99 | **2.60** | -| isort 40000 | **0.02** | 2.97 | 36.63 | 7.66 | 8.38 | 2.04 | 1.27 | -| qsort 800000 | **0.15** | 1.16 | 97.30 | 2.32 | 1.82 | 0.56 | 0.35 | -| msort 800000 | 0.46 | 1.00 | 98.27 | 1.23 | 1.37 | 0.41 | **0.33** | +| ack(3,11) | 2.31 | **0.41** | - | 4.42 | 3.53 | 0.83 | 0.72 | +| fib 38 | 1.60 | **0.26** | 8.49 | 2.30 | 2.83 | 0.40 | 0.41 | +| bsort 40000 | 34.81 | 11.17 | 76.72 | 17.64 | 16.92 | 2.95 | **2.51** | +| isort 40000 | **0.02** | 2.97 | 36.63 | 6.72 | 8.34 | 1.15 | 1.23 | +| qsort 800000 | **0.15** | 1.16 | 97.30 | 6.07 | 1.81 | 0.63 | 0.36 | +| msort 800000 | 0.46 | 1.00 | 98.27 | 3.92 | 1.36 | 0.46 | **0.34** | - **Comparison in execution time** with other implementations: **Haskell** (GHC version 8.10.7), **Standard ML of New Jersey** v110.74 (interpreter mode) and **Python** 3.8.5 in execution time. @@ -39,16 +39,18 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you wri - [Interactive mode (single-thread version)](#interactive-mode-single-thread-version) - [Interactive mode (multi-thread version)](#interactive-mode-multi-thread-version) - [Batch mode and sample files](#batch-mode-and-sample-files) - - [Execution Options](#execution-options) * [Introduction to Programming in Inpla](#introduction-to-programming-in-inpla) * [Commands](#commands) +* [Execution Options](#execution-options) * [Updates](#updates) * [Publications](#publications) * [Related Works](#related-works) * [License](#license) + ## Getting Started + * Requirement - gcc (>= 4.0), flex, bison @@ -73,7 +75,7 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you wri ``` $ ./inpla - Inpla 0.7.3 : Interaction nets as a programming language [built: 20 Feb. 2022] + Inpla 0.8.0 : Interaction nets as a programming language [built: 27 Feb. 2022] >>> ``` @@ -130,7 +132,7 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you wri ``` $ ./inpla -f sample/gcd.in - Inpla 0.7.3 : Interaction nets as a programming language [built: 20 Feb. 2022] + Inpla 0.8.0 : Interaction nets as a programming language [built: 27 Feb. 2022] (4 interactions, 0.00 sec) 7 @@ -163,7 +165,7 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you wri ``` $ ./inpla -f sample/isort.in - Inpla 0.7.3 : Interaction nets as a programming language [built: 20 Feb. 2022] + Inpla 0.8.0 : Interaction nets as a programming language [built: 27 Feb. 2022] (16 interactions, 0.00 sec) [1,2,3,6,9] @@ -233,7 +235,7 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you wri ``` $ ./inpla -f sample/qsort.in - Inpla 0.7.3 : Interaction nets as a programming language [built: 20 Feb. 2022] + Inpla 0.8.0 : Interaction nets as a programming language [built: 27 Feb. 2022] (22 interactions, 0.00 sec) [1,2,3,6,9] @@ -253,30 +255,6 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you wri -### Execution Options - -* When invoking Inpla, you can specify the following options: - - ``` - $ ./inpla -h - Inpla version 0.7.3 - Usage: inpla [options] - - Options: - -f Set input file name (Defalut: STDIN) - -e Set the unit size of the EQ stack (Default: 256) - -w Enable Weak Reduction strategy (Default: false) - -t Set the number of threads (Default: 8) - -d = Bind to - -h Print this help message - ``` - -**Note**: - -* The option `-w` is available for the single-thread version. -* The option ```-t``` is available for the multi-thread version that is compiled by ```make thread```. The default value is setting for the number of cores, so execution will be automatically scaled without specifying this. - - # Introduction to Programming in Inpla #### Contents in this section @@ -817,16 +795,68 @@ Inpla has the following macro: +## Execution Options + +* When invoking Inpla, you can specify the following options: + + ``` + $ ./inpla -h + Inpla version 0.8.0 + Usage: inpla [options] + + -f Set input file name (Defalut: STDIN) + -d = Bind to + -Xms Set initial heap size to 2^ (Defalut: 12 (=4096)) + -Xmt Set increasing heap times to 2^ (Defalut: 3 (= 8)) + 0: the same size heap is inserted when it runs up. + 1: the twice (=2^1) size heap is inserted. + -Xes Set initial equation stack size (Default: 256) + -w Enable Weak Reduction strategy (Default: false) + -t Set the number of threads (Default: 8) + + -h Print this help message + ``` + +**Note**: + +* The option `-w` is available for the single-thread version. +* The option ```-t``` is available for the multi-thread version that is compiled by ```make thread```. The default value is setting for the number of cores, so execution will be automatically scaled without specifying this. + + + + ## Updates See [Changelog.md](Changelog.md) for details. + +### v0.8.0 (released on 27 February 2022) + +#### New Features: + +* **Flexibly expandable ring buffer for agents and names**: We can change the size of buffers that are inserted when all of nodes run up, though it was fixed before. It is possible to start a small heap for small computation, and it can be expanded for larger computation. + + ![speedup-ratio](pic/flexibily_expandable.png) + + * To set the initial size to 2^*n*, use the execution option `-Xms n` (default `n` is 12, so the size is 4096): + * To set the increasing magnification to 2^*n*, use the option `-Xmt n` (default `n` is 3, so the inserted heap is 8 times of the run up heap) + + To use the fixed sized ring buffer, comment out the following definition in `src/inpla.y`: + + ``` + #define EXPANDABLE_HEAP // Expandable heaps for agents and names + ``` + + + + + ### v0.7.0 (released on 30 January 2022) #### New Features: -- **Logical operators on integers**: Not `!` (`not`), And `&&` (`and`) and Or `||` (`or`) are available. Only `0` is regarded as False and these operators return `1` for Truth, `0` for False. -- **Bytecode optimisations**: Bytecodes are optimised by Copy propagation, Dead code elimination methods. See [Changelog.md](Changelog.md) for more details. +* **Logical operators on integers**: Not `!` (`not`), And `&&` (`and`) and Or `||` (`or`) are available. Only `0` is regarded as False and these operators return `1` for Truth, `0` for False. +* **Bytecode optimisations**: Bytecodes are optimised by Copy propagation, Dead code elimination methods. See [Changelog.md](Changelog.md) for more details. @@ -834,13 +864,13 @@ See [Changelog.md](Changelog.md) for details. #### New Features: -- **Introduced new data structure for ring buffers for agents and names**: The ring buffers are automatically expanded when all elements of these are used up. See [Changelog.md](Changelog.md) for more details. +* **Introduced new data structure for ring buffers for agents and names**: The ring buffers are automatically expanded when all elements of these are used up. See [Changelog.md](Changelog.md) for more details. ### Logo of Inpla (relased on 27 December 2021) -- A logo is released as an idea: +* A logo is released as an idea: ![inpla-logo](pic/inpla-logo.png) diff --git a/comparison/Inpla/main.sh b/comparison/Inpla/main.sh index fbf11c4..f7935fb 100644 --- a/comparison/Inpla/main.sh +++ b/comparison/Inpla/main.sh @@ -13,7 +13,7 @@ bash ./sptestInpla.sh src/isort-40000.in bash ./sptestInpla.sh src/isort-40000-reuse.in bash ./sptestInpla.sh src/qsort-800000.in -bash ./sptestInpla.sh src/qsort-800000-reuse.in +bash ./sptestInpla.sh src/qsort-800000-reuse.in '-Xms 18 -Xmt 0' bash ./sptestInpla.sh src/msort-800000.in -bash ./sptestInpla.sh src/msort-800000-reuse.in +bash ./sptestInpla.sh src/msort-800000-reuse.in '-Xms 18 -Xmt 0' diff --git a/comparison/Inpla/sptestInpla.sh b/comparison/Inpla/sptestInpla.sh index 90f7436..833606a 100644 --- a/comparison/Inpla/sptestInpla.sh +++ b/comparison/Inpla/sptestInpla.sh @@ -9,6 +9,7 @@ ct=10 waittime=5 max_threads=9 +min_threads=1 # options source=$1 @@ -129,7 +130,7 @@ puts_header $log "$source $opt" do_experiment "./$inpla_seq -f $path_source $opt" "non-thread" # Execution in parallel -for ((thread=1; thread<=max_threads; thread++)) +for ((thread=min_threads; thread<=max_threads; thread++)) do do_experiment "./$inpla_para -f $path_source $opt -t $thread" "-t $thread" done diff --git a/pic/benchmark_reuse_v0.7.3.png b/pic/benchmark_reuse_v0.7.3.png deleted file mode 100644 index da943ae..0000000 Binary files a/pic/benchmark_reuse_v0.7.3.png and /dev/null differ diff --git a/pic/benchmark_reuse_v0.8.0.png b/pic/benchmark_reuse_v0.8.0.png new file mode 100644 index 0000000..41ba902 Binary files /dev/null and b/pic/benchmark_reuse_v0.8.0.png differ diff --git a/pic/flexibily_expandable.png b/pic/flexibily_expandable.png new file mode 100644 index 0000000..13d3e9b Binary files /dev/null and b/pic/flexibily_expandable.png differ diff --git a/src/.#-emacsFibRvc b/src/.#-emacsFibRvc new file mode 100644 index 0000000..05bf541 --- /dev/null +++ b/src/.#-emacsFibRvc @@ -0,0 +1 @@ +shinya@DESKTOP-O24CQQG.3520:1645438118 \ No newline at end of file diff --git a/src/.#-emacsGvT7Q7 b/src/.#-emacsGvT7Q7 new file mode 100644 index 0000000..036dd55 --- /dev/null +++ b/src/.#-emacsGvT7Q7 @@ -0,0 +1 @@ +shinya@DESKTOP-O24CQQG.16996:1645692483 \ No newline at end of file diff --git a/src/.#-emacsd3nZKL b/src/.#-emacsd3nZKL new file mode 100644 index 0000000..65cefa4 --- /dev/null +++ b/src/.#-emacsd3nZKL @@ -0,0 +1 @@ +shinya@DESKTOP-O24CQQG.4372:1645518580 \ No newline at end of file diff --git a/src/id_table.h b/src/id_table.h index 02ac9e6..fa27cfb 100644 --- a/src/id_table.h +++ b/src/id_table.h @@ -11,8 +11,10 @@ #define ID_INT 0 -// builtin を加えたら void IdTable_init() 内で -// IdTable に arity と 表示方法の登録を忘れないように！ + +// NOTE: +// For a NEW BUILT-IN AGENT, +// STORE the ARITY on IdTable in the function IdTable_init()! #define ID_TUPLE0 1 #define ID_TUPLE1 2 #define ID_TUPLE2 3 diff --git a/src/inpla.y b/src/inpla.y index 87e39b8..44cd821 100644 --- a/src/inpla.y +++ b/src/inpla.y @@ -32,6 +32,9 @@ #ifdef OPTIMISE_IMCODE // the following depends on the definition OPTIMISE_IMCODE #define OPTIMISE_IMCODE_TRO // Optimise option for Tail Recursive Opt. + //#define OPTIMISE_TWO_ADDRESS // Generate codes for two address notation + //#define OPTIMISE_TWO_ADDRESS_MKAGENT2 // MKAGENT2 also. Arithmetic also. + #endif @@ -49,8 +52,8 @@ //#define COUNT_MKAGENT // count of execution fo mkagent -#define VERSION "0.7.3-1" -#define BUILT_DATE "24 Feb. 2022" +#define VERSION "0.8.0" +#define BUILT_DATE "27 Feb. 2022" // ------------------------------------------------------------------ @@ -61,11 +64,19 @@ // For threads --------------------------------- +#ifndef EXPANDABLE_HEAP +static int MaxThreadsNum=1; // The old heap uses it to divide total numbers. +#endif + #ifdef THREAD + +#ifdef EXPANDABLE_HEAP +static int MaxThreadsNum=1; +#endif + #include extern int pthread_setconcurrency(int concurrency); -static int MaxThreadsNum=1; static int SleepingThreadsNum=0; // for cas spinlock @@ -590,23 +601,28 @@ int yyerror(char *s) { #ifdef EXPANDABLE_HEAP // HOOP_SIZE must be power of two -#define HOOP_SIZE (1 << 18) -#define HOOP_SIZE_MASK ((HOOP_SIZE) -1) +//#define INIT_HOOP_SIZE (1 << 10) +//#define HOOP_SIZE_INCREASE_TIMES 1<<4 // increased by 16 times + +//#define INIT_HOOP_SIZE (1 << 12) // 2^12 = 4096 +//#define HOOP_SIZE_INCREASE_TIMES 1<<3 // increased by 8 times + +static unsigned int Hoop_init_size = 12; // 2^12 = 4096 +static unsigned int Hoop_increasing_magnitude = 3; // 2^3 = 8 + typedef struct HoopList_tag { VALUE *hoop; struct HoopList_tag *next; + unsigned int size; // NOTE: Be power of 2! } HoopList; -// Nodes with '1' on the 31bit in hoops are ready for use and -// '0' are occupied, that is to say, using now. -#define HOOPFLAG_READYFORUSE 0x01 << 31 -#define IS_READYFORUSE(a) ((a) & HOOPFLAG_READYFORUSE) -#define SET_HOOPFLAG_READYFORUSE(a) ((a) = ((a) | HOOPFLAG_READYFORUSE)) -#define RESET_HOOPFLAG_READYFORUSE_AGENT(a) ((a) = (HOOPFLAG_READYFORUSE)) -#define RESET_HOOPFLAG_READYFORUSE_NAME(a) ((a) = ((ID_NAME) | (HOOPFLAG_READYFORUSE))) -#define TOGGLE_HOOPFLAG_READYFORUSE(a) ((a) = ((a) ^ HOOPFLAG_READYFORUSE)) +#define HOOPFLAG_READYFORUSE 0 +#define IS_READYFORUSE(a) ((a)==HOOPFLAG_READYFORUSE) +#define SET_HOOPFLAG_READYFORUSE(a) ((a)=HOOPFLAG_READYFORUSE) +#define RESET_HOOPFLAG_READYFORUSE_AGENT(a) ((a)=HOOPFLAG_READYFORUSE) +#define RESET_HOOPFLAG_READYFORUSE_NAME(a) ((a)=HOOPFLAG_READYFORUSE) typedef struct Heap_tag { @@ -616,8 +632,7 @@ typedef struct Heap_tag { -HoopList *HoopList_new_forName(void) { - int i; +HoopList *HoopList_new_forName(unsigned int size) { HoopList *hp_list; hp_list = (HoopList *)malloc(sizeof(HoopList)); @@ -627,17 +642,17 @@ HoopList *HoopList_new_forName(void) { } - // Name Heap - hp_list->hoop = (VALUE *)malloc(sizeof(Name) * HOOP_SIZE); + // Name Heap + hp_list->hoop = (VALUE *)malloc(size * sizeof(Name)); if (hp_list->hoop == (VALUE *)NULL) { printf("[HoopList->Hoop (name)]Malloc error\n"); exit(-1); - } - for (i=0; ihoop))[i].basic.id = ID_NAME; + } + for (int i=0; ihoop))[i].basic.id); } - + hp_list->size = size; + // hp->next = NULL; // this should be executed only for the first creation. return hp_list; } @@ -645,10 +660,17 @@ HoopList *HoopList_new_forName(void) { -HoopList *HoopList_new_forAgent(void) { - int i; +HoopList *HoopList_new_forAgent(unsigned int size) { HoopList *hp_list; + + // #define PUT_NEW_AGENTHOOP_TIME +#ifdef PUT_NEW_AGENTHOOP_TIME + unsigned long long t, time; + start_timer(&t); +#endif + + hp_list = (HoopList *)malloc(sizeof(HoopList)); if (hp_list == NULL) { printf("[HoopList]Malloc error\n"); @@ -657,16 +679,25 @@ HoopList *HoopList_new_forAgent(void) { // Agent Heap - hp_list->hoop = (VALUE *)malloc(sizeof(Agent) * HOOP_SIZE); + hp_list->hoop = (VALUE *)malloc(size * sizeof(Agent)); if (hp_list->hoop == (VALUE *)NULL) { printf("[HoopList->Hoop]Malloc error\n"); exit(-1); } - for (i=0; ihoop))[i].basic.id); - } + hp_list->size = size; + + +#ifdef PUT_NEW_AGENTHOOP_TIME + time=stop_timer(&t); + printf("(%.6f sec)\n", + (double)(time)/1000000.0); +#endif + + // hp->next = NULL; // this should be executed only for the first creation. return hp_list; } @@ -686,7 +717,7 @@ unsigned long Heap_GetNum_Usage_forAgent(Heap *hp) { do { hoop = (Agent *)(hoop_list->hoop); - for (int i = 0; i < HOOP_SIZE; i++) { + for (int i = 0; i < hoop_list->size; i++) { if (!IS_READYFORUSE(hoop[i].basic.id)) { count++; } @@ -708,7 +739,7 @@ unsigned long Heap_GetNum_Usage_forName(Heap *hp) { do { hoop = (Name *)(hoop_list->hoop); - for (int i = 0; i < HOOP_SIZE; i++) { + for (int i = 0; i < hoop_list->size; i++) { if (!IS_READYFORUSE(hoop[i].basic.id)) { count++; } @@ -737,10 +768,10 @@ VALUE myalloc_Agent(Heap *hp) { while (1) { hoop = (Agent *)(hoop_list->hoop); - while (idx < HOOP_SIZE) { + while (idx < hoop_list->size) { if (IS_READYFORUSE(hoop[idx].basic.id)) { - TOGGLE_HOOPFLAG_READYFORUSE(hoop[idx].basic.id); + // TOGGLE_HOOPFLAG_READYFORUSE(hoop[idx].basic.id); hp->last_alloc_idx = idx; //hp->last_alloc_idx = (idx-1+HOOP_SIZE)%HOOP_SIZE_MASK; @@ -774,12 +805,14 @@ VALUE myalloc_Agent(Heap *hp) { // new last_alloc // -->|......|-->|oooooo|-->|......|-- + // printf("(Agent hoop is expanded [%d])\n", hoop_list->size); #ifdef VERBOSE_HOOP_EXPANSION puts("(Agent hoop is expanded)"); #endif HoopList *new_hoop_list; - new_hoop_list = HoopList_new_forAgent(); + unsigned int new_size_p2 = hoop_list->size * Hoop_increasing_magnitude; + new_hoop_list = HoopList_new_forAgent(new_size_p2); HoopList *last_alloc = hoop_list->next; hoop_list->next = new_hoop_list; @@ -815,17 +848,19 @@ VALUE myalloc_Name(Heap *hp) { while (1) { hoop = (Name *)(hoop_list->hoop); - - while (idx < HOOP_SIZE) { + int size = hoop_list->size; + + while (idx < size) { if (IS_READYFORUSE(hoop[idx].basic.id)) { - TOGGLE_HOOPFLAG_READYFORUSE(hoop[idx].basic.id); + // TOGGLE_HOOPFLAG_READYFORUSE(hoop[idx].basic.id); - //hp->last_alloc_idx = idx; - hp->last_alloc_idx = (idx-1+HOOP_SIZE) & HOOP_SIZE_MASK; + //hp->last_alloc_idx = idx; + hp->last_alloc_idx = (idx-1+ size) & (size-1); hp->last_alloc_list = hoop_list; + // printf("%d\n", hp->last_alloc_idx); exit(1); // printf("hit[%d]\n", idx); return (VALUE)&(hoop[idx]); } @@ -857,7 +892,8 @@ VALUE myalloc_Name(Heap *hp) { #endif HoopList *new_hoop_list; - new_hoop_list = HoopList_new_forName(); + unsigned int new_size_p2 = hoop_list->size * Hoop_increasing_magnitude; + new_hoop_list = HoopList_new_forName(new_size_p2); HoopList *last_alloc = hoop_list->next; hoop_list->next = new_hoop_list; @@ -960,7 +996,7 @@ VALUE myalloc_Agent(Heap *hp) { } continue; } - TOGGLE_HEAPFLAG_READYFORUSE(hp_heap[idx].basic.id); + // TOGGLE_HEAPFLAG_READYFORUSE(hp_heap[idx].basic.id); hp->lastAlloc = idx; @@ -997,7 +1033,7 @@ VALUE myalloc_Name(Heap *hp) { continue; } // TOGGLE_HEAPFLAG_READYFORUSE(((Name *)hp->heap)[idx].basic.id); - TOGGLE_HEAPFLAG_READYFORUSE(hp_heap[idx].basic.id); + // TOGGLE_HEAPFLAG_READYFORUSE(hp_heap[idx].basic.id); hp->lastAlloc = idx; @@ -1039,7 +1075,8 @@ unsigned long Heap_getnum_used_forAgent(Heap *hp) { //static inline void myfree(VALUE ptr) { - TOGGLE_HEAPFLAG_READYFORUSE(BASIC(ptr)->id); + // TOGGLE_HEAPFLAG_READYFORUSE(BASIC(ptr)->id); + SET_HEAPFLAG_READYFORUSE(BASIC(ptr)->id); } @@ -1438,23 +1475,36 @@ static VirtualMachine VM; #ifdef COUNT_MKAGENT unsigned int NumberOfMkAgent; - // unsigned int id; #endif #ifdef EXPANDABLE_HEAP void VM_Buffer_Init(VirtualMachine * restrict vm) { // Agent Heap - vm->agentHeap.last_alloc_list = HoopList_new_forAgent(); + /* + vm->agentHeap.last_alloc_list = HoopList_new_forAgent(Hoop_init_size); vm->agentHeap.last_alloc_list->next = vm->agentHeap.last_alloc_list; vm->agentHeap.last_alloc_idx = 0; - + */ + + vm->agentHeap.last_alloc_list = HoopList_new_forAgent(Hoop_init_size); + vm->agentHeap.last_alloc_list->next = HoopList_new_forAgent(Hoop_init_size); + vm->agentHeap.last_alloc_list->next->next = vm->agentHeap.last_alloc_list; + vm->agentHeap.last_alloc_idx = 0; + // Name Heap - vm->nameHeap.last_alloc_list = HoopList_new_forName(); + /* + vm->nameHeap.last_alloc_list = HoopList_new_forName(Hoop_init_size); vm->nameHeap.last_alloc_list->next = vm->nameHeap.last_alloc_list; vm->nameHeap.last_alloc_idx = 0; - + */ + + vm->nameHeap.last_alloc_list = HoopList_new_forName(Hoop_init_size); + vm->nameHeap.last_alloc_list->next = HoopList_new_forName(Hoop_init_size); + vm->nameHeap.last_alloc_list->next->next = vm->nameHeap.last_alloc_list; + vm->nameHeap.last_alloc_idx = 0; + // Register vm->reg = malloc(sizeof(VALUE) * VM_REG_SIZE); } @@ -1574,6 +1624,7 @@ VALUE make_Name(VirtualMachine * restrict vm) { VALUE ptr; ptr = myalloc_Name(&vm->nameHeap); + AGENT(ptr)->basic.id = ID_NAME; NAME(ptr)->port = (VALUE)NULL; return ptr; @@ -1945,7 +1996,7 @@ typedef enum { OP_NOP, // These are used for translation from intermediate codes to Bytecodes - OP_LABEL, OP_DEAD_CODE, OP_BEGIN_BLOCK, + OP_LABEL, OP_DEAD_CODE, OP_BEGIN_BLOCK, OP_BEGIN_JMPCNCT_BLOCK, OP_LOAD_META // keep dest as it is } Code; @@ -2078,7 +2129,7 @@ void IMCode_puts(int n) { "NOP", - "LABEL", "__DEAD_CODE", "BEGIN_BLOCK", + "LABEL", "__DEAD_CODE", "BEGIN_BLOCK", "BEGIN_CNCT_BLOCK", "LOAD_META" @@ -2098,8 +2149,9 @@ void IMCode_puts(int n) { // for indentation case OP_LABEL: case OP_BEGIN_BLOCK: + case OP_BEGIN_JMPCNCT_BLOCK: break; - + default: printf("\t"); } @@ -2212,6 +2264,7 @@ void IMCode_puts(int n) { case OP_BEGIN_BLOCK: + case OP_BEGIN_JMPCNCT_BLOCK: printf("%s:\n", string_opcode[imcode->opcode]); break; @@ -2358,20 +2411,35 @@ void VMCode_puts(void **code, int n) { i+=2; } else if (code[i] == CodeAddr[OP_MKAGENT1]) { +#ifndef OPTIMISE_TWO_ADDRESS printf("mkagent1 id:%lu reg%lu reg%lu\n", (unsigned long)code[i+1], (unsigned long)code[i+2], (unsigned long)code[i+3]); i+=3; +#else + printf("mkagent1 id:%lu reg%lu\n", + (unsigned long)code[i+1], + (unsigned long)code[i+2]); + i+=2; +#endif } else if (code[i] == CodeAddr[OP_MKAGENT2]) { +#ifndef OPTIMISE_TWO_ADDRESS_MKAGENT2 printf("mkagent2 id:%lu reg%lu reg%lu reg%lu\n", (unsigned long)code[i+1], (unsigned long)code[i+2], (unsigned long)code[i+3], (unsigned long)code[i+4]); i+=4; - +#else + printf("mkagent2 id:%lu reg%lu reg%lu\n", + (unsigned long)code[i+1], + (unsigned long)code[i+2], + (unsigned long)code[i+3]); + i+=3; +#endif + } else if (code[i] == CodeAddr[OP_MKAGENT3]) { printf("mkagent3 id:%lu reg%lu reg%lu reg%lu reg%lu\n", (unsigned long)code[i+1], @@ -2773,6 +2841,11 @@ typedef struct { int label; // labels int tmpRegState[VM_REG_SIZE]; // register assignments // store localvar numbers. -1 is no assignment. + +#ifdef OPTIMISE_TWO_ADDRESS_MKAGENT2 + int jmpcnctBlockRegState[VM_REG_SIZE]; + int is_in_jmpcnctBlock; +#endif } CmEnvironment; @@ -2808,6 +2881,23 @@ void CmEnv_clear_bind(int preserve_idx) { CmEnv.bindPtr = preserve_idx+1; } +#ifdef OPTIMISE_TWO_ADDRESS_MKAGENT2 +void CmEnv_clear_jmpcnctBlock_assignment_table_all(void) { + for (int i=0; i= VM_OFFSET_LOCALVAR) + CmEnv.tmpRegState[reg] = -1; +#else + + +#ifndef OPTIMISE_TWO_ADDRESS_MKAGENT2 + if (reg >= VM_OFFSET_LOCALVAR) + CmEnv.tmpRegState[reg] = -1; +#else + + if (CmEnv.is_in_jmpcnctBlock) { + CmEnv.jmpcnctBlockRegState[reg] = -1; + return; + } else { + // if (reg >= VM_OFFSET_LOCALVAR) + CmEnv.tmpRegState[reg] = -1; + } +#endif +#endif +} + + + + +#ifdef OPTIMISE_TWO_ADDRESS +int CmEnv_assign_reg(int localvar, int reg) { + // Enforce assignment of localvar to reg. + // [Return values] + // When the reg has been already used, + // this function returns a new reg. + // Otherwise it returns -1. + + int *tmpRegState; + +#ifndef OPTIMISE_TWO_ADDRESS_MKAGENT2 + tmpRegState = CmEnv.tmpRegState; +#else + + if (CmEnv.is_in_jmpcnctBlock) { + tmpRegState = CmEnv.jmpcnctBlockRegState; + } else { + tmpRegState = CmEnv.tmpRegState; + } +#endif + + if (tmpRegState[reg] == localvar) { + return -1; + } + + if (tmpRegState[reg] < 0) { + tmpRegState[reg] = localvar; + return -1; + } + + + int orig_var = tmpRegState[reg]; + + tmpRegState[reg] = localvar; + + int new_reg = CmEnv_get_newreg(orig_var); + return new_reg; + +} +#endif int CmEnv_Optimise_check_occurence_in_block(int localvar, @@ -3102,8 +3306,33 @@ int CmEnv_Optimise_check_occurence_in_block(int localvar, // This optimisation will last until OP_BEGIN_BLOCK return 0; } + +#ifdef OPTIMISE_TWO_ADDRESS_MKAGENT2 + if ((CmEnv.is_in_jmpcnctBlock) && + (imcode->opcode == OP_BEGIN_JMPCNCT_BLOCK)) { + // This optimisation will last until OP_BEGIN_JMPCNCT_BLOCK + return 0; + } +#endif + switch (imcode->opcode) { + case OP_LOAD_META: + // LOAD_META src dest + // If `localvar' occurs as `dest', it should not be freed. + if (imcode->operand2 == localvar) { + return 1; + } + + case OP_LOAD: + case OP_LOADI: + // OP src1 dest + if (imcode->operand1 == localvar) { + return 1; + } + break; + + case OP_MKNAME: case OP_MKGNAME: break; @@ -3177,15 +3406,6 @@ int CmEnv_Optimise_check_occurence_in_block(int localvar, } break; - case OP_LOAD: - case OP_LOADI: - case OP_LOAD_META: - // OP src1 dest - if (imcode->operand1 == localvar) { - return 1; - } - break; - case OP_MUL: case OP_DIV: case OP_MOD: @@ -3243,13 +3463,6 @@ int CmEnv_Optimise_check_occurence_in_block(int localvar, } -void CmEnv_free_reg(int reg) { - if (reg >= VM_OFFSET_LOCALVAR) - CmEnv.tmpRegState[reg] = -1; -} - - - int CmEnv_Optimise_VMCode_CopyPropagation_LOADI(int target_imcode_addr) { struct IMCode_tag *imcode; @@ -3258,13 +3471,17 @@ int CmEnv_Optimise_VMCode_CopyPropagation_LOADI(int target_imcode_addr) { load_i = IMCode[target_imcode_addr].operand1; load_to = IMCode[target_imcode_addr].operand2; - for (int i=target_imcode_addr+1; iopcode == OP_BEGIN_BLOCK) { // This optimisation will last until OP_BEGIN_BLOCK return 0; } + // if (imcode->opcode == OP_BEGIN_JMPCNCT_BLOCK) { + // // This optimisation will last until OP_BEGIN_BLOCK + // return 0; + // } switch (imcode->opcode) { @@ -3394,13 +3611,18 @@ int CmEnv_Optimise_VMCode_CopyPropagation(int target_imcode_addr) { } - for (int i=target_imcode_addr+1; iopcode == OP_BEGIN_BLOCK) { // This optimisation will last until OP_BEGIN_BLOCK return 0; } + // if ((CmEnv.is_in_jmpcnctBlock) && + // (imcode->opcode == OP_BEGIN_JMPCNCT_BLOCK)) { + // // This optimisation will last until OP_BEGIN_JMPCNCT_BLOCK + // return 0; + // } switch (imcode->opcode) { @@ -3600,25 +3822,25 @@ int CmEnv_generate_VMCode(void **code) { CmEnv_clear_register_assignment_table_all(); #endif - for (int i=0; i [reg2/reg1] - // and Dead Code Elimination + // Copy Propagation for OP_LOAD reg1, reg2 --> [reg2/reg1]. + // When it is success, the code is applied Dead Code Elimination to. if (imcode->opcode == OP_LOAD) { - if (CmEnv_Optimise_VMCode_CopyPropagation(i)) { + if (CmEnv_Optimise_VMCode_CopyPropagation(line_num)) { continue; } } if (imcode->opcode == OP_LOAD_META) { - if (CmEnv_Optimise_VMCode_CopyPropagation(i)) { + if (CmEnv_Optimise_VMCode_CopyPropagation(line_num)) { continue; } } if (imcode->opcode == OP_LOADI) { - if (CmEnv_Optimise_VMCode_CopyPropagation_LOADI(i)) { + if (CmEnv_Optimise_VMCode_CopyPropagation_LOADI(line_num)) { continue; } } @@ -3660,8 +3882,7 @@ int CmEnv_generate_VMCode(void **code) { int dest = imcode->operand2; #ifdef OPTIMISE_IMCODE - if (imcode->opcode != OP_REUSEAGENT0) - dest = CmEnv_get_newreg(dest); + dest = CmEnv_get_newreg(dest); #endif code[addr++] = CodeAddr[imcode->opcode]; @@ -3677,17 +3898,29 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, line_num)) CmEnv_free_reg(src1); - if (imcode->opcode != OP_REUSEAGENT1) - dest = CmEnv_get_newreg(dest); +#ifndef OPTIMISE_TWO_ADDRESS + dest = CmEnv_get_newreg(dest); +#else + int new_reg = CmEnv_assign_reg(dest, src1); + if (new_reg > 0) { + code[addr++] = CodeAddr[OP_LOAD]; + code[addr++] = (void *)(unsigned long)src1; + code[addr++] = (void *)(unsigned long)new_reg; + } +#endif #endif + code[addr++] = CodeAddr[imcode->opcode]; code[addr++] = (void *)(unsigned long)imcode->operand1; code[addr++] = (void *)(unsigned long)src1; - code[addr++] = (void *)(unsigned long)dest; +#ifndef OPTIMISE_TWO_ADDRESS + code[addr++] = (void *)(unsigned long)dest; +#endif + break; } case OP_MKAGENT2: { @@ -3701,24 +3934,38 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE + src2 = CmEnv_using_reg(src2); + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, line_num)) + && (imcode->operand2 != imcode->operand3)) { + CmEnv_free_reg(src2); + } + +#ifndef OPTIMISE_TWO_ADDRESS_MKAGENT2 + dest = CmEnv_get_newreg(dest); +#else + int new_reg = CmEnv_assign_reg(dest, src2); + if (new_reg > 0) { + code[addr++] = CodeAddr[OP_LOAD]; + code[addr++] = (void *)(unsigned long)src2; + code[addr++] = (void *)(unsigned long)new_reg; + } +#endif + src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, i)) - && (imcode->operand2 != imcode->operand3)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, line_num)) CmEnv_free_reg(src1); - src2 = CmEnv_using_reg(src2); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, i)) - CmEnv_free_reg(src2); - - if (imcode->opcode != OP_REUSEAGENT2) - dest = CmEnv_get_newreg(dest); + #endif + code[addr++] = CodeAddr[imcode->opcode]; code[addr++] = (void *)(unsigned long)imcode->operand1; code[addr++] = (void *)(unsigned long)src1; code[addr++] = (void *)(unsigned long)src2; +#ifndef OPTIMISE_TWO_ADDRESS_MKAGENT2 code[addr++] = (void *)(unsigned long)dest; +#endif break; } @@ -3734,22 +3981,21 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, line_num)) && (imcode->operand2 != imcode->operand3) && (imcode->operand2 != imcode->operand4)) CmEnv_free_reg(src1); src2 = CmEnv_using_reg(src2); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, line_num)) && (imcode->operand3 != imcode->operand4)) CmEnv_free_reg(src2); src3 = CmEnv_using_reg(src3); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, line_num)) CmEnv_free_reg(src3); - if (imcode->opcode != OP_REUSEAGENT3) - dest = CmEnv_get_newreg(dest); + dest = CmEnv_get_newreg(dest); #endif code[addr++] = CodeAddr[imcode->opcode]; @@ -3773,29 +4019,28 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, line_num)) && (imcode->operand2 != imcode->operand3) && (imcode->operand2 != imcode->operand4) && (imcode->operand2 != imcode->operand5)) CmEnv_free_reg(src1); src2 = CmEnv_using_reg(src2); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, line_num)) && (imcode->operand3 != imcode->operand4) && (imcode->operand3 != imcode->operand5)) CmEnv_free_reg(src2); src3 = CmEnv_using_reg(src3); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, line_num)) && (imcode->operand4 != imcode->operand5)) CmEnv_free_reg(src3); src4 = CmEnv_using_reg(src4); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, line_num)) CmEnv_free_reg(src4); - if (imcode->opcode != OP_REUSEAGENT4) - dest = CmEnv_get_newreg(dest); + dest = CmEnv_get_newreg(dest); #endif @@ -3821,7 +4066,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, line_num)) && (imcode->operand2 != imcode->operand3) && (imcode->operand2 != imcode->operand4) && (imcode->operand2 != imcode->operand5) @@ -3829,29 +4074,28 @@ int CmEnv_generate_VMCode(void **code) { CmEnv_free_reg(src1); src2 = CmEnv_using_reg(src2); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, line_num)) && (imcode->operand3 != imcode->operand4) && (imcode->operand3 != imcode->operand5) && (imcode->operand3 != imcode->operand6)) CmEnv_free_reg(src2); src3 = CmEnv_using_reg(src3); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, line_num)) && (imcode->operand4 != imcode->operand5) && (imcode->operand4 != imcode->operand6)) CmEnv_free_reg(src3); src4 = CmEnv_using_reg(src4); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, line_num)) && (imcode->operand5 != imcode->operand6)) CmEnv_free_reg(src4); src5 = CmEnv_using_reg(src5); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand6, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand6, line_num)) CmEnv_free_reg(src5); - if (imcode->opcode != OP_REUSEAGENT5) - dest = CmEnv_get_newreg(dest); + dest = CmEnv_get_newreg(dest); #endif code[addr++] = CodeAddr[imcode->opcode]; @@ -3867,13 +4111,11 @@ int CmEnv_generate_VMCode(void **code) { case OP_REUSEAGENT0: { - // printf("OP_MKAGENT0 var%d id:%d\n", + // printf("OP_REUSEAGENT0 var%d id:%d\n", // imcode->operand1, imcode->operand2); int dest = imcode->operand1; #ifdef OPTIMISE_IMCODE - if (imcode->opcode != OP_REUSEAGENT0) - dest = CmEnv_get_newreg(dest); #endif code[addr++] = CodeAddr[imcode->opcode]; @@ -3883,18 +4125,15 @@ int CmEnv_generate_VMCode(void **code) { } case OP_REUSEAGENT1: { - // printf("OP_MKAGENT1 var%d id:%d var%d\n", + // printf("OP_REUSEAGENT1 var%d id:%d var%d\n", // imcode->operand1, imcode->operand2, imcode->operand3); int dest = imcode->operand1; int src1 = imcode->operand3; #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, line_num)) CmEnv_free_reg(src1); - - if (imcode->opcode != OP_REUSEAGENT1) - dest = CmEnv_get_newreg(dest); #endif code[addr++] = CodeAddr[imcode->opcode]; @@ -3905,10 +4144,6 @@ int CmEnv_generate_VMCode(void **code) { } case OP_REUSEAGENT2: { - // printf("OP_MKAGENT2 var%d id:%d var%d var%d\n", - // imcode->operand1, imcode->operand2, - // imcode->operand3, imcode->operand4); - int dest = imcode->operand1; int src1 = imcode->operand3; int src2 = imcode->operand4; @@ -3916,16 +4151,14 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, i)) - && (imcode->operand3 != imcode->operand4)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, line_num)) + && (imcode->operand3 != imcode->operand4)) { CmEnv_free_reg(src1); + } src2 = CmEnv_using_reg(src2); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, line_num)) CmEnv_free_reg(src2); - - if (imcode->opcode != OP_REUSEAGENT2) - dest = CmEnv_get_newreg(dest); #endif code[addr++] = CodeAddr[imcode->opcode]; @@ -3938,7 +4171,7 @@ int CmEnv_generate_VMCode(void **code) { } case OP_REUSEAGENT3: { - // printf("OP_MKAGENT3 var%d id:%d var%d var%d var%d\n", + // printf("OP_REUSEAGENT3 var%d id:%d var%d var%d var%d\n", // imcode->operand1, imcode->operand2, // imcode->operand3, imcode->operand4, imcode->operand5); int dest = imcode->operand1; @@ -3949,22 +4182,19 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, line_num)) && (imcode->operand3 != imcode->operand4) && (imcode->operand3 != imcode->operand5)) CmEnv_free_reg(src1); src2 = CmEnv_using_reg(src2); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, line_num)) && (imcode->operand4 != imcode->operand5)) CmEnv_free_reg(src2); src3 = CmEnv_using_reg(src3); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, i)) - CmEnv_free_reg(src3); - - if (imcode->opcode != OP_REUSEAGENT3) - dest = CmEnv_get_newreg(dest); + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, line_num)) + CmEnv_free_reg(src3); #endif code[addr++] = CodeAddr[imcode->opcode]; @@ -3978,7 +4208,7 @@ int CmEnv_generate_VMCode(void **code) { } case OP_REUSEAGENT4: { - // printf("OP_MKAGENT3 var%d id:%d var%d var%d var%d\n", + // printf("OP_REUSEAGENT3 var%d id:%d var%d var%d var%d\n", // imcode->operand1, imcode->operand2, // imcode->operand3, imcode->operand4, imcode->operand5); int dest = imcode->operand1; @@ -3989,29 +4219,26 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, line_num)) && (imcode->operand3 != imcode->operand4) && (imcode->operand3 != imcode->operand5) && (imcode->operand3 != imcode->operand6)) CmEnv_free_reg(src1); src2 = CmEnv_using_reg(src2); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, line_num)) && (imcode->operand4 != imcode->operand5) && (imcode->operand4 != imcode->operand6)) CmEnv_free_reg(src2); src3 = CmEnv_using_reg(src3); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, line_num)) && (imcode->operand5 != imcode->operand6)) CmEnv_free_reg(src3); src4 = CmEnv_using_reg(src4); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand6, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand6, line_num)) CmEnv_free_reg(src4); - - if (imcode->opcode != OP_REUSEAGENT4) - dest = CmEnv_get_newreg(dest); #endif @@ -4025,7 +4252,7 @@ int CmEnv_generate_VMCode(void **code) { break; } case OP_REUSEAGENT5: { - // printf("OP_MKAGENT3 var%d id:%d var%d var%d var%d\n", + // printf("OP_REUSEAGENT3 var%d id:%d var%d var%d var%d\n", // imcode->operand1, imcode->operand2, // imcode->operand3, imcode->operand4, imcode->operand5); int dest = imcode->operand1; @@ -4037,7 +4264,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand3, line_num)) && (imcode->operand3 != imcode->operand4) && (imcode->operand3 != imcode->operand5) && (imcode->operand3 != imcode->operand6) @@ -4045,29 +4272,26 @@ int CmEnv_generate_VMCode(void **code) { CmEnv_free_reg(src1); src2 = CmEnv_using_reg(src2); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, line_num)) && (imcode->operand4 != imcode->operand5) && (imcode->operand4 != imcode->operand6) && (imcode->operand4 != imcode->operand7)) CmEnv_free_reg(src2); src3 = CmEnv_using_reg(src3); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, line_num)) && (imcode->operand5 != imcode->operand6) && (imcode->operand5 != imcode->operand7)) CmEnv_free_reg(src3); src4 = CmEnv_using_reg(src4); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand6, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand6, line_num)) && (imcode->operand6 != imcode->operand7)) CmEnv_free_reg(src4); src5 = CmEnv_using_reg(src5); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand7, i)) - CmEnv_free_reg(src5); - - if (imcode->opcode != OP_REUSEAGENT5) - dest = CmEnv_get_newreg(dest); + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand7, line_num)) + CmEnv_free_reg(src5); #endif code[addr++] = CodeAddr[imcode->opcode]; @@ -4088,12 +4312,17 @@ int CmEnv_generate_VMCode(void **code) { int src1 = imcode->operand1; int dest = imcode->operand2; -#ifdef OPTIMISE_IMCODE +#ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); dest = CmEnv_get_newreg(dest); + + if (src1 == dest) { + imcode->opcode = OP_DEAD_CODE; + break; + } #endif code[addr++] = CodeAddr[imcode->opcode]; @@ -4111,10 +4340,20 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); // dest = CmEnv_get_newreg(dest); + +#ifdef OPTIMISE_TWO_ADDRESS_MKAGENT2 + int a=CmEnv_assign_reg(dest, dest); +#endif + + if (src1 == dest) { + imcode->opcode = OP_DEAD_CODE; + break; + } + #endif code[addr++] = CodeAddr[OP_LOAD]; @@ -4150,12 +4389,26 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE + src1 = CmEnv_using_reg(src1); + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) + && (imcode->operand1 != imcode->operand2)) + CmEnv_free_reg(src1); + + src2 = CmEnv_using_reg(src2); + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, line_num)) + && (imcode->operand1 != imcode->operand2)) + CmEnv_free_reg(src2); + + /* src1 = CmEnv_using_reg(src1); if (imcode->operand1 != imcode->operand2) CmEnv_free_reg(src1); src2 = CmEnv_using_reg(src2); CmEnv_free_reg(src2); + */ + + #endif code[addr++] = CodeAddr[imcode->opcode]; @@ -4172,7 +4425,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); #endif @@ -4209,12 +4462,12 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) && (imcode->operand1 != imcode->operand2)) CmEnv_free_reg(src1); src2 = CmEnv_using_reg(src2); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, line_num)) CmEnv_free_reg(src2); dest = CmEnv_get_newreg(dest); @@ -4236,7 +4489,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); dest = CmEnv_get_newreg(dest); @@ -4258,7 +4511,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); dest = CmEnv_get_newreg(dest); @@ -4282,12 +4535,12 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) && (imcode->operand1 != imcode->operand2)) CmEnv_free_reg(src1); src2 = CmEnv_using_reg(src2); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, line_num)) CmEnv_free_reg(src2); #endif @@ -4301,15 +4554,16 @@ int CmEnv_generate_VMCode(void **code) { // op src1 int2 #ifdef OPTIMISE_IMCODE - if ((imcode->operand2 == 0) && (IMCode[i+1].opcode == OP_JMPEQ0_R0)) { + if ((imcode->operand2 == 0) + && (IMCode[line_num+1].opcode == OP_JMPEQ0_R0)) { // OP_EQI_Ro reg1 $0 // OP_JMPEQ0_R0 pc // ==> // DEAD_CODE // OP_JMPNEQ reg1 pc - IMCode[i+1].opcode = OP_JMPNEQ0; - IMCode[i+1].operand2 = IMCode[i+1].operand1; - IMCode[i+1].operand1 = imcode->operand1; + IMCode[line_num+1].opcode = OP_JMPNEQ0; + IMCode[line_num+1].operand2 = IMCode[line_num+1].operand1; + IMCode[line_num+1].operand1 = imcode->operand1; imcode->opcode = OP_DEAD_CODE; break; } @@ -4320,7 +4574,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); #endif @@ -4341,7 +4595,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); dest = CmEnv_get_newreg(dest); @@ -4359,7 +4613,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); #endif @@ -4392,7 +4646,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); #endif @@ -4410,7 +4664,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); #endif @@ -4428,7 +4682,7 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) CmEnv_free_reg(src1); #endif @@ -4461,12 +4715,12 @@ int CmEnv_generate_VMCode(void **code) { #ifdef OPTIMISE_IMCODE src1 = CmEnv_using_reg(src1); - if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, i)) + if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand1, line_num)) && (imcode->operand1 != imcode->operand2)) CmEnv_free_reg(src1); src2 = CmEnv_using_reg(src2); - if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, i)) + if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, line_num)) CmEnv_free_reg(src2); #endif @@ -4485,6 +4739,17 @@ int CmEnv_generate_VMCode(void **code) { #endif break; + +#ifdef OPTIMISE_TWO_ADDRESS_MKAGENT2 + case OP_BEGIN_JMPCNCT_BLOCK: + // CmEnv_clear_jmpcnctBlock_assignment_table_all(); + + CmEnv_stack_assignment_table(); + CmEnv.is_in_jmpcnctBlock = 1; + break; +#endif + + case OP_LABEL: if (imcode->operand1 > MAX_LABEL) { printf("Critical Error: Label number overfllow."); @@ -4884,7 +5149,8 @@ void Ast_make_annotation_TailRecursionOptimisation(Ast *mainbody) { if (mainbody == NULL) return; - + + if (mainbody->id == AST_BODY) { Ast *body = mainbody; @@ -5685,15 +5951,11 @@ int Compile_eqlist_on_ast(Ast *at) { } else if (eq->id == AST_CNCT_TRO) { - // Pealing (*L) Ast *eq_lhs = eq->left; // (*L)(AGENT(Fib, arglist)) Ast *deconst_term = eq_lhs->left; // (AGENT(Fib, arglist)) - // printf("TRO: %s><%s\n", deconst_term->left->sym, eq->right->left->sym); - - int eq_rhs_name_reg = CmEnv_find_var(eq->right->left->sym); @@ -5709,7 +5971,10 @@ int Compile_eqlist_on_ast(Ast *at) { IMCode_genCode3(OP_JMPCNCT, eq_rhs_name_reg, CmEnv.idR, label1); } - + +#ifdef OPTIMISE_TWO_ADDRESS_MKAGENT2 + IMCode_genCode0(OP_BEGIN_JMPCNCT_BLOCK); +#endif // int var1 = Compile_term_on_ast(deconst_term, -1); int var1 = Compile_term_on_ast(eq_lhs, -1); @@ -5720,6 +5985,10 @@ int Compile_eqlist_on_ast(Ast *at) { // prevent putting FREE_L, and ignore counting up for name ref CmEnv.annotateL = ANNOTATE_TRO; +#ifdef OPTIMISE_TWO_ADDRESS_MKAGENT2 + IMCode_genCode0(OP_BEGIN_JMPCNCT_BLOCK); +#endif + IMCode_genCode1(OP_LABEL, label1); @@ -5735,6 +6004,9 @@ int Compile_eqlist_on_ast(Ast *at) { arg_list = ast_getTail(arg_list); } for (int i=0; iright->left; idL = get_ruleagentID(ruleAgent_L); } - + // Annotation (*L)、(*R) の処理があるため @@ -6486,18 +6759,20 @@ int make_rule(Ast *ast) { #ifdef OPTIMISE_IMCODE_TRO Ast_make_annotation_TailRecursionOptimisation(rule_mainbody); #endif - - + if (!Compile_rule_mainbody_on_ast(rule_mainbody)) return 0; - // #define MKRULE_DEBUG + // #define MKRULE_DEBUG #ifndef MKRULE_DEBUG gencode_num += CmEnv_generate_VMCode(&code[2]); #else puts("-----------------------------------"); + printf("Rule: %s(id:%d) >< %s(id:%d).\n", + IdTable_get_name(idL), idL, + IdTable_get_name(idR), idR); IMCode_puts(0); gencode_num += CmEnv_generate_VMCode(&code[2]); IMCode_puts(0); @@ -6582,7 +6857,7 @@ void sweep_AgentHeap(Heap *hp) { do { hoop = (Agent *)(hoop_list->hoop); - for (int i = 0; i < HOOP_SIZE; i++) { + for (int i = 0; i < hoop_list->size; i++) { if (!IS_FLAG_MARKED(hoop[i].basic.id)) { SET_HOOPFLAG_READYFORUSE(hoop[i].basic.id); @@ -6601,7 +6876,7 @@ void sweep_NameHeap(Heap *hp) { do { hoop = (Name *)(hoop_list->hoop); - for (int i = 0; i < HOOP_SIZE; i++) { + for (int i = 0; i < hoop_list->size; i++) { if (!IS_FLAG_MARKED(hoop[i].basic.id)) { SET_HOOPFLAG_READYFORUSE(hoop[i].basic.id); @@ -6830,15 +7105,25 @@ void *exec_code(int mode, VirtualMachine * restrict vm, void * restrict *code) { goto *code[pc]; E_MKAGENT1: +#ifndef OPTIMISE_TWO_ADDRESS // puts("mkagent1 id src1 dest"); pc++; a1 = make_Agent(vm, (unsigned long)code[pc++]); AGENT(a1)->port[0] = reg[(unsigned long)code[pc++]]; reg[(unsigned long)code[pc++]] = a1; +#else + // puts("mkagent1 id dest"); + pc++; + a1 = make_Agent(vm, (unsigned long)code[pc++]); + AGENT(a1)->port[0] = reg[(unsigned long)code[pc]]; + reg[(unsigned long)code[pc++]] = a1; +#endif + goto *code[pc]; E_MKAGENT2: +#ifndef OPTIMISE_TWO_ADDRESS_MKAGENT2 // puts("mkagent2 id src1 src2 dest"); pc++; a1 = make_Agent(vm, (unsigned long)code[pc++]); @@ -6848,6 +7133,17 @@ void *exec_code(int mode, VirtualMachine * restrict vm, void * restrict *code) { a1port[1] = reg[(unsigned long)code[pc++]]; } reg[(unsigned long)code[pc++]] = a1; +#else + // puts("mkagent2 id src1 dest"); + pc++; + a1 = make_Agent(vm, (unsigned long)code[pc++]); + { + volatile VALUE *a1port = AGENT(a1)->port; + a1port[0] = reg[(unsigned long)code[pc++]]; + a1port[1] = reg[(unsigned long)code[pc]]; + } + reg[(unsigned long)code[pc++]] = a1; +#endif goto *code[pc]; @@ -7457,7 +7753,7 @@ void *exec_code(int mode, VirtualMachine * restrict vm, void * restrict *code) { E_JMPCNCT: - // puts("JMPCNCT reg id pc"); + // puts("JMPCNCT reg id pc"); #ifdef COUNT_CNCT Count_cnct++; #endif @@ -7552,27 +7848,17 @@ void *exec_code(int mode, VirtualMachine * restrict vm, void * restrict *code) { E_CNCTGN: - // puts("CNCTGN reg reg"); + // puts("CNCTGN reg reg"); // "x"~s, "x"->t ==> push(s,t), free("x") where "x" is a global name. - /* - { - pc++; - VALUE x = reg[(unsigned long)code[pc++]]; - a1 = NAME(x)->port; - free_Name(x); - PUSH(vm, reg[(unsigned long)code[pc++]], a1); - } - goto *code[pc]; - */ { VALUE x = reg[(unsigned long)code[pc+1]]; a1 = NAME(x)->port; free_Name(x); VALUE t = reg[(unsigned long)code[pc+2]]; - puts("============================================"); - puts_term(t);printf("\n~");puts_term(a1);puts(""); - puts("============================================"); + // puts("============================================"); + // puts_term(t);printf("\n~");puts_term(a1);puts(""); + // puts("============================================"); PUSH(vm, t, a1); } @@ -7580,6 +7866,7 @@ void *exec_code(int mode, VirtualMachine * restrict vm, void * restrict *code) { goto *code[pc]; + E_SUBSTGN: // puts("SUBSTGN reg reg"); @@ -7610,6 +7897,134 @@ void *exec_code(int mode, VirtualMachine * restrict vm, void * restrict *code) { +void exec_code_fib(VirtualMachine * restrict vm) { + VALUE a1; + VALUE *reg = vm->reg; + + + // 0000: jmpneq0 reg12 $4 + { + int i = reg[12]; + if (FIX2INT(i)) { + goto LABEL_0007; + } + } + + // 0003: pushi reg1 $0 + { + VALUE a1 = reg[1]; + VALUE a2 = INT2FIX(0); + PUSH(vm, a1, a2); + } + + // 0006: ret_free_l + free_Agent(reg[VM_OFFSET_ANNOTATE_L]); + return; + + // 0007: eqi_r0 reg12 $1 +LABEL_0007: + { + int i = reg[12]; + int j = INT2FIX(1); + + if (i==j) { + reg[0] = 1; + } else { + reg[0] = 0; + } + } + + // 0010: jmpeq0_r0 $4 + { + int i = reg[0]; + if (!i) { + goto LABEL_0016; + } + } + + + // 0012: pushi reg1 $1 + { + VALUE a1 = reg[1]; + VALUE a2 = INT2FIX(1); + PUSH(vm, a1, a2); + } + + // 0015: ret_free_l + free_Agent(reg[VM_OFFSET_ANNOTATE_L]); + return; + + + // 0016: mkname reg13 +LABEL_0016: + reg[13] = make_Name(vm); + + + // 0018: reuseagent2 reg11 as id=18 reg1 reg13 + a1 = reg[11]; + AGENT(a1)->basic.id = 18; + { + /* + volatile VALUE *a1port = AGENT(a1)->port; + a1port[0] = reg[1]; + a1port[1] = reg[13]; + */ + AGENT(a1)->port[0] = reg[1]; + AGENT(a1)->port[1] = reg[13]; + } + + + // 0023: mkagent1 id:28 reg11 reg14 + a1 = make_Agent(vm, 28); + AGENT(a1)->port[0] = reg[11]; + reg[14] = a1; + + + // 0027: dec reg12 reg15 + { + int i = FIX2INT(reg[12]); + + reg[15] = INT2FIX(--i); + } + + + // 0030: push reg14 reg15 + { + VALUE a1 = reg[14]; + VALUE a2 = reg[15]; + PUSH(vm, a1, a2); + } + + + // 0033: mkagent1 id:28 reg13 reg13 + a1 = make_Agent(vm, 28); + AGENT(a1)->port[0] = reg[13]; + reg[13] = a1; + + + // 0037: subi reg12 $2 reg14 + { + int i = FIX2INT(reg[12]); + int j = 2; + + reg[14] = INT2FIX(i-j); + } + + + // 0041: push reg13 reg14 + { + VALUE a1 = reg[13]; + VALUE a2 = reg[14]; + PUSH(vm, a1, a2); + } + + + // 0044: ret + return; + +} + + // ------------------------------------------------------------ @@ -7783,6 +8198,20 @@ loop_a2IsFixnum: #endif } + /* + if (BASIC(a1)->id == 28) { + vm->reg[VM_OFFSET_METAVAR_L(0)] = AGENT(a1)->port[0]; + + vm->reg[VM_OFFSET_ANNOTATE_L] = a1; + vm->reg[VM_OFFSET_ANNOTATE_R] = a2; + + COUNTUP_INTERACTION(vm); + exec_code_fib(vm); + + return; + } + */ + int i; unsigned long arity; arity = (unsigned long)code[0]; @@ -8451,12 +8880,13 @@ int exec(Ast *at) { // aplist at = at->right; - // for aplists - // puts(""); ast_puts(at); puts(""); - Ast_RewriteOptimisation_eqlist(at); - // puts(""); ast_puts(at); puts(""); - // exit(1); + // for aplists + // puts(""); ast_puts(at); puts(""); + // Ast_RewriteOptimisation_eqlist(at); + // puts(""); ast_puts(at); puts(""); + // // exit(1); + Ast_RewriteOptimisation_eqlist(at); // Syntax error check @@ -8514,7 +8944,6 @@ int exec(Ast *at) { CmEnv_retrieve_MKGNAME(); CmEnv_generate_VMCode(code); - /* // for debug CmEnv_retrieve_MKGNAME(); @@ -8525,7 +8954,6 @@ int exec(Ast *at) { // end for debug */ - #ifdef COUNT_MKAGENT NumberOfMkAgent=0; #endif @@ -8622,7 +9050,7 @@ void *tpool_thread(void *arg) { // printf("Thread%d works on Core%d/%d\n", vm->id, (vm->id)%CpuNum, CpuNum-1); #endif - + while (1) { VALUE t1, t2; @@ -8694,6 +9122,8 @@ void tpool_init(unsigned int agentBufferSize, unsigned int eqstack_size) { for (i=0; iid = i; + + // usleep(i*2); #ifdef EXPANDABLE_HEAP VM_Init(VMs[i], eqstack_size); @@ -8941,30 +9371,120 @@ int main(int argc, char *argv[]) printf("Inpla version %s\n", VERSION); puts("Usage: inpla [options]\n"); puts("Options:"); - printf(" -f Set input file name (Defalut: STDIN)\n"); + printf(" -f Set input file name (Defalut: STDIN)\n"); + printf(" -d = Bind to \n"); + #ifndef EXPANDABLE_HEAP //v0.5.6 - printf(" -c Set the size of heaps (Defalut: %8u)\n", heap_size); -#endif + printf(" -c Set size of heaps (Defalut: %10u)\n", heap_size); +#else + printf(" -Xms Set initial heap size to 2^ (Defalut: %2u (=%4u))\n", + Hoop_init_size, 1 << Hoop_init_size); + printf(" -Xmt Set increasing heap times to 2^ (Defalut: %2u (=%4u))\n", + Hoop_increasing_magnitude, 1 << Hoop_increasing_magnitude); + printf(" 0: the same size heap is inserted when it runs up.\n"); + printf(" 1: the twice (=2^1) size heap is inserted.\n"); - printf(" -e Set the unit size of the EQ stack (Default: %8u)\n", max_EQStack); +#endif + + printf(" -Xes Set initial equation stack size (Default: %10u)\n", max_EQStack); - // Special Options -#ifdef THREAD - printf(" -t Set the number of threads (Default: %8d)\n", MaxThreadsNum); + + +#ifdef THREAD + printf(" -t Set the number of threads (Default: %10d)\n", MaxThreadsNum); #else - printf(" -w Enable Weak Reduction strategy (Default: false)\n"); + printf(" -w Enable Weak Reduction strategy (Default: false)\n"); #endif - - printf(" -d = Bind to \n"); - printf(" -h Print this help message\n\n"); + + + + printf(" -h Print this help message\n\n"); exit(-1); break; + case 'X': + if (!(strcmp(argv[i], "-Xes"))) { + i++; + if (i < argc) { + param = atoi(argv[i]); + if (param == 0) { + printf("ERROR: '%s' is illegal parameter for -Xes\n", argv[i]); + exit(-1); + } + } else { + printf("ERROR: The option '-Xes' needs a natural number."); + exit(-1); + } + max_EQStack=param; + } + + +#ifdef EXPANDABLE_HEAP + else if (!(strcmp(argv[i], "-Xms"))) { + i++; + if (i < argc) { + int valid = 1; + char *val = argv[i]; + + for (int idx = 0; idx < strlen(val); idx++) { + if ((val[idx] < '0') || (val[idx] > '9')) { + valid = 0; + break; + } + } + if (!valid) { + printf("ERROR: '%s' is illegal parameter for -Xms\n", argv[i]); + exit(-1); + } + + param = atoi(argv[i]); + if (param == 0) { + printf("ERROR: '%s' is illegal parameter for -Xms\n", argv[i]); + exit(-1); + } + } else { + printf("ERROR: The option '-Xms' needs a number."); + exit(-1); + } + Hoop_init_size = param; + + + } else if (!(strcmp(argv[i], "-Xmt"))) { + i++; + if (i < argc) { + + + int valid = 1; + char *val = argv[i]; + + for (int idx = 0; idx < strlen(val); idx++) { + if ((val[idx] < '0') || (val[idx] > '9')) { + valid = 0; + break; + } + } + if (!valid) { + printf("ERROR: '%s' is illegal parameter for -Xmt\n", argv[i]); + exit(-1); + } + + } else { + printf("ERROR: The option '-Xmt' needs a number."); + exit(-1); + } + param = atoi(argv[i]); + Hoop_increasing_magnitude = param; + + } +#endif + break; + + case 'd': i++; if (i < argc) { @@ -9010,7 +9530,7 @@ int main(int argc, char *argv[]) ast_recordConst(varname, atoi(val)); } else { - puts("ERROR: The option switch '-d' needs a string such as VarName=value."); + puts("ERROR: The option '-d' needs a string such as VarName=value."); exit(-1); } break; @@ -9021,7 +9541,7 @@ int main(int argc, char *argv[]) fname = argv[i]; retrieve_flag = 0; } else { - printf("ERROR: The option switch '-f' needs a string of an input file name."); + printf("ERROR: The option '-f' needs a string of an input file name."); exit(-1); } break; @@ -9038,29 +9558,14 @@ int main(int argc, char *argv[]) exit(-1); } } else { - printf("ERROR: The option switch '-c' needs a number as an argument."); + printf("ERROR: The option '-c' needs a number as an argument."); exit(-1); } heap_size=param; break; #endif - - - case 'e': - i++; - if (i < argc) { - param = atoi(argv[i]); - if (param == 0) { - printf("ERROR: '%s' is illegal parameter for -e\n", argv[i]); - exit(-1); - } - } else { - printf("ERROR: The option switch '-e' needs a natural number."); - exit(-1); - } - max_EQStack=param; - break; - + + #ifdef THREAD case 't': @@ -9072,7 +9577,7 @@ int main(int argc, char *argv[]) exit(-1); } } else { - printf("ERROR: The option switch '-t' needs a number of threads."); + printf("ERROR: The option '-t' needs a number of threads."); exit(-1); } @@ -9126,10 +9631,23 @@ int main(int argc, char *argv[]) #ifndef EXPANDABLE_HEAP // v0.5.6 - heap_size = heap_size/MaxThreadsNum; + heap_size = heap_size/MaxThreadsNum; + +#else + Hoop_init_size = 1 << Hoop_init_size; + Hoop_increasing_magnitude = 1 << Hoop_increasing_magnitude; #endif - + + /* + // check parameters + printf("Hoop_init_size=%d\n", Hoop_init_size); + printf("Hoop_increasing_magnitude=%d\n", Hoop_increasing_magnitude); + printf("max_EQStack=%d\n", max_EQStack); + exit(1); + */ + + IdTable_init(); NameTable_init(); RuleTable_init(); -- cgit v1.2.3