FIND A SOLUTION AT Academic Writers Bay

optimiser_e

Description

You must complete the implementation of the optimiser-e program in the file optimiser-e.cpp.

The program reads an XML representation of an abstract syntax tree of a Jack class from standard input, using ast_parse_xml() and writes an optimised version to standard output, using ast_print_as_xml().

Startup Files

The main function in the optimiser-e.cpp file reads an abstract syntax tree of a Jack class from standard input using the function ast_parse_xml(). It then passes the tree to the function optimise_class() that uses the functions described in abstract-syntax-tree.h to make a complete optimised copy of the abstract syntax tree of the class. You must modify the optimise_*() functions to add code that will replace expressions or parts of an expression with their final result if it is known.

Any code that walks the abstract syntax tree of a class will be very similar in structure so the startup files should save you a lot of typing. However, you do not need to follow this structure if you do not want to and you can delete any functions you are not going to use. You must not modify the main() function but you can modify the remainder of the code as much as you like.

Compiling and Running

When the Makefile attempts to compile the program optimiser-e, it will use the file optimiser-e.cpp.

The program can be compiled and run against the provided tests using the command:

% make test 3optimiser-e

make will only compile the program if it has not yet been compiled or the source files have changed since it was last compiled.

Note: Do not modify the provided Makefile or the sub-directories bin, includes or lib. These will be replaced during testing by the web submission system.

Expression Optimisation

One advantage of having a parser produce an abstract syntax tree is that optimisations can be applied to the abstract syntax tree before code generation. The purpose of the optimiser-e program is to make a copy of an abstract syntax tree and where possible, replace expressions or parts of expressions with their final result if it is known. That is, if the result of an expression can be calculated by the optimiser, the expression is simply replaced by its result.

Expression Nodes

The abstract syntax tree we are using represents expressions as a vector with an odd number of elements that start with a term node and alternates between term nodes and infix operator nodes. Prior to attempting to optimise an expression we first need to apply the optimiser to each of its terms, that is, we recursively make optimised copies all the child nodes first. This means that when we attempt to optimise an expression, all of its constituent terms have already been optimised.

Term Classification

In describing the optimisations to be implemented we first classify each of the term nodes based on the child node that they contain. This list :

X – expression: the child node can be anything.

E – expression with no calls or divides by 0: if the child’s sub-tree contains no subroutine calls and contains no divides by 0.

V – a variable: if the child node is a variable node.

C – a constant: if the child node is an integer or boolean constant or the child node is a unary op containing a term node which is also a constant. The value used is the constant’s integer value (true is -1, false is 0) or the result of applying the unary operator to its child constant.

0: can be classified as a constant and has value 0.

1: can be classified as a constant and has value 1.

false: can be classified as a constant and has value 0.

true: can be classified as a constant and has value -1.

Note:

a term classified as 0, 1, false or true is also classified as a C, an E and an X.

a term classified as a constant, C, is also classified as an E and an X.

a term classified as a variable, V, is also classified as an E and an X.

a term classified as an expression, E, is also classified as an X.

the logical operators ‘~’, ‘|’ and ‘&’ all operate bit-wise on their arguments so the optimiser can safely treat all integer and boolean constants as integer values without affecting the correctness of any operations. Expressions that mix integers and bit-wise logical operations frequently appear in system programming tasks.

it is important to distinguish terms that may contain subroutine calls because they could cause state changes to the program. Any optimisations that unexpectedly affected whether or not those calls occurred would undermine the programmer’s ability to reason about the behaviour of their programs and must be avoided.

Redundant Expression Nodes

When we need to optimise an expression node, e1, that contains a single term node, t1, that contains an expression, e2, expression node e1 and term node t1 are both redundant. In this case we simply replace expression node e1 with expression node e2.

Redundant Term Nodes

When we need to optimise a term node, t1, where the child node is an expression that contains a single term node, t2, term node t1 and the expression node are both redundant. In this case we simply replace term node t1 with term node t2.

When we need to optimise a term node, t1, where the child node is a unary op node, u1, that contains a term node, t2, that also contains a unary op, u2, using the same operator, the nodes t1, u1, t2 and u2 are all redundant. In this case we replace term node t1 with the child term node from u2.

Unary Expression Optimisations

When we need to optimise a term node, t1, where the child node is a unary op node, u1, that contains a term node, t2, that can be classified as a constant, we replace term node t1 with the result of evaluating the unary operation.

Notes:

All expression evaluation must match the results that would be obtained on a Hack computer, that is, all arithmetic is performed in 16-bit two’s complement binary.

The results of a unary not, ‘~‘, operation that has the values 0 or -1 must be represented as the boolean constants false and true respectively.

All other results of a unary not operation must be expressed as an integer.

The result of a unary minus, ‘–‘, operation must be expressed as an integer.

The ast_int node abstract syntax tree will accept any 16-bit integer value.

Expression Optimisations

Once all the term nodes within an expression have been copied (optimised) we then have the challenge of working out what optimisations to apply. Central to this question are the issues of order of evaluation and operator precedence, that is, in what order do we evaluate the component terms in an expression and in what order do we apply the infix operators?

For the purposes of this assignment we will only optimise infix expressions. Therefore, any expression containing more than one infix operator will not be optimised after the term nodes have been copied (optimised).

During the optimisation process each infix expression must be considered for optimisation. The following table shows all the optimisations that should be applied based on the combination of infix operation and the term node classification of the left and right operands:

Original Expression

Copied / Optimised Expression

Before

After

C1 + C2

R

3 + 7

10

X + 0

X

x + 0

x

0 + X

X

0 + z

z

C1 – C2

R

7 – 2

5

X – 0

X

x() – 0

x()

V – V

c – c

C1 * C2

R

2 * 3

6

X * 1

X

zz() * 1

zz()

1 * X

X

1 * g

g

E * 0

x * 0

0 * E

0 * x

X / 0

X / 0

w() / 0

w() / 0

C1 / C2

R

5 / 2

2

X / 1

X

n / 1

n

C1 | C2

R

4 | 1

5

true | E

true

true | false

true

E | true

true

false | true

true

V | V

V

a | a

a

C1 & C2

R

5 & 4

4

false & E

false

false & true

false

E & false

false

true & false

false

V & V

V

a & a

a

C1 = C2

R

12 = 54

false

V = V

true

a = a

true

C1 < C2

R

3 < 6

true

V < V

false

x < x

false

C1 > C2

R

13 > 6

true

V > V

false

x > x

false

Note:

If an infix expression matches more than one optimisation case, only the first one applies.

C1 and C2 may or may not be the same constants.

When V appears twice it refers to the same variable.

An operation that divides an expression by 0 is not optimised.

R represents the result of evaluating the original expression.

All expression evaluation must match the results that would be obtained on a Hack computer, that is, all arithmetic is performed in 16-bit two’s complement binary.

The results of a bit-wise logical and, ‘&‘, or, or, ‘|‘, operations that have the values 0 or -1 must be represented as the boolean constants false and true respectively.

All other results of a bit-wise logical operation must be expressed as an integer.

The ast_int node abstract syntax tree will accept any 16-bit integer value.

The results of all comparison operations must be expressed as one of the boolean constants false and true

Do not modify the main() function in optimiser-e.cpp.

- Assignment status: Already Solved By Our Experts
*(USA, AUS, UK & CA PhD. Writers)***CLICK HERE TO GET A PROFESSIONAL WRITER TO WORK ON THIS PAPER AND OTHER SIMILAR PAPERS, GET A NON PLAGIARIZED PAPER FROM OUR EXPERTS**

QUALITY: 100% ORIGINAL PAPER – **NO PLAGIARISM** – CUSTOM PAPER