From 8386c6b9e98f4de5850129d4ba3a24af3b669599 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Tam=C3=A1s=20Hadh=C3=A1zy?= <85063808+Hels15@users.noreply.github.com> Date: Sat, 21 Sep 2024 08:59:52 +0100 Subject: extend chapter 2 peephole section (#118) * extend peephole section * fix bad indentatitons * Update README.md --- chapter02/README.md | 111 ++++++++++++++++++++- chapter02/docs/02-demonstration-peephole.svg | 54 ++++++++++ .../docs/02-demonstration-pre-peephole-nokill.svg | 100 +++++++++++++++++++ chapter02/docs/02-demonstration-pre-peephole.svg | 87 ++++++++++++++++ 4 files changed, 351 insertions(+), 1 deletion(-) create mode 100644 chapter02/docs/02-demonstration-peephole.svg create mode 100644 chapter02/docs/02-demonstration-pre-peephole-nokill.svg create mode 100644 chapter02/docs/02-demonstration-pre-peephole.svg (limited to 'chapter02') diff --git a/chapter02/README.md b/chapter02/README.md index 4bc72523..14eef8b2 100644 --- a/chapter02/README.md +++ b/chapter02/README.md @@ -127,7 +127,6 @@ starting in [Chapter 4](../chapter04/README.md) and [Chapter There are other important properties of the Lattice that we discuss in [Chapter 4](../chapter04/README.md) and [Chapter 10](../chapter10/README.md), such as the "meet" and "join" operators and their rules. - ## Nodes Pre Peephole Optimization The following visual shows how the graph looks like pre-peephole optimization: @@ -142,3 +141,113 @@ The following visual shows how the graph looks like pre-peephole optimization: ## Post-peephole ![Example Visual](./docs/02-post-peephole-ex1.svg) + +## Demonstration +To demonstrate how the optimisation works, let's consider the following code: +``` +return 1+2; +``` +This is parsed as: +```java + var lhs = parseMultiplication(); + if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); +``` +When the peephole is called on the AddNode node it first calls the compute function: +```java + public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); +``` +```java + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()+i1.value()); + } + return Type.BOTTOM; + } +``` +In our case both of the operands(`1`, `2`) are constants, and instance of +`TypeInteger`. +Since `compute` returns a type, and we know that both of our operands are constants, we can do +constant propagation/folding where we compute the result of the expression so that instead of having `1+2` we can +have `3`. + +The 'TypeInteger' interface inherits from type but also has a field that stores the value observed for that type. +```java + private final long _con +``` + +AddNode has the layout: + +![Example Visual](./docs/02-demonstration-pre-peephole.svg) + +Since, we already know the value of both of the operands, we can just add them together and replace the +old node with a constant node that just holds the result of the expression. + +To do this - we have to recognize this happens when the type computed for the node is already a constant, but the node +is still not an instance of constant node. + +This can be captured by: +```java +// Replace constant computations from non-constants with a constant node +if (!(this instanceof ConstantNode) && type.isConstant()) { +} +``` +Note how we return a constant type when doing constant folding +```java +return TypeInteger.constant(i0.value()+i1.value()); +``` +We can create a constant node in the following way: +```java +return new ConstantNode(type).peephole(); +``` +This recursively calls the peephole algorithm. +Now, we end up with this: + +![Example Visual](./docs/02-demonstration-pre-peephole-nokill.svg) + +Notice, how we added the constant node holding a constant value of `3`. +The remaining add node is unused and can be killed. + +We can call the kill function before this way: +```java +// Replace constant computations from non-constants with a constant node +if (!(this instanceof ConstantNode) && type.isConstant()) { + kill(); // Kill `this` because replacing with a Constant + return new ConstantNode(type).peephole(); +``` +This is responsible for deleting the dangling add node. + +```java +public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + for( int i=0; i + + + + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con_5 + +#3 + + + +Con_5->Start1 + + +0 + + + +Return6 + +Return + + + +Return6->Start1 + + +0 + + + +Return6->Con_5 + + +1 + + + \ No newline at end of file diff --git a/chapter02/docs/02-demonstration-pre-peephole-nokill.svg b/chapter02/docs/02-demonstration-pre-peephole-nokill.svg new file mode 100644 index 00000000..3d4f53df --- /dev/null +++ b/chapter02/docs/02-demonstration-pre-peephole-nokill.svg @@ -0,0 +1,100 @@ + + + + + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con_2 + +#1 + + + +Con_2->Start1 + + +0 + + + +Con_3 + +#2 + + + +Con_3->Start1 + + +0 + + + +Add4 + ++ + + + +Add4->Con_2 + + +1 + + + +Add4->Con_3 + + +2 + + + +Con_5 + +#3 + + + +Con_5->Start1 + + +0 + + + +Return6 + +Return + + + +Return6->Start1 + + +0 + + + +Return6->Con_5 + + +1 + + + \ No newline at end of file diff --git a/chapter02/docs/02-demonstration-pre-peephole.svg b/chapter02/docs/02-demonstration-pre-peephole.svg new file mode 100644 index 00000000..49624652 --- /dev/null +++ b/chapter02/docs/02-demonstration-pre-peephole.svg @@ -0,0 +1,87 @@ + + + + + + +chapter02 + + +cluster_Nodes + + + + +Start1 + +Start + + + +Con_2 + +#1 + + + +Con_2->Start1 + + +0 + + + +Con_3 + +#2 + + + +Con_3->Start1 + + +0 + + + +Add4 + ++ + + + +Add4->Con_2 + + +1 + + + +Add4->Con_3 + + +2 + + + +Return5 + +Return + + + +Return5->Start1 + + +0 + + + +Return5->Add4 + + +1 + + + \ No newline at end of file -- cgit v1.2.3