=============================
CPE Part 14: Constant Folding						[TOC]
=============================

---- VIDEO ------------------------------
https://www.youtube.com/embed/ysXGEnV0bds
-----------------------------------------

Example for Constant Folding
============================
---- SHELL (path=session23/git/abc, hide) --------------------------------------
git pull
make
--------------------------------------------------------------------------------

Here a simple example where constant folding can be applied:

:import: session23/git/abc/examples/fold_example.abc

---- SHELL (path=session23/git/abc) --------------------------------------------
./xtest_abc fold_example.s fold_example.tex < examples/fold_example.abc
--------------------------------------------------------------------------------

How constant folding was applied can be seen in the __generated PDF__.

---- SHELL (path=session23/git/abc, hide) --------------------------------------
lualatex fold_example.tex
cp fold_example.pdf /home/www/htdocs/numerik/hpc/ss22/hpc0/session23/
--------------------------------------------------------------------------------


:links: generated PDF -> https://www.mathematik.uni-ulm.de/numerik/hpc/ss22/hpc0/session23/fold_example.pdf


Changes to the Expression Interface
===================================
We add two function declarations to the interface. Function _isConstExpr()_
returns _true_ if an expression hold a constant. In our case this is currently
equivalent to check whether the expression kind is an unsigned integer literal.
Function _constFoldExpr()_ can be used to apply constant folding to an
expression tree. It returns a pointer to the original expression tree if no
folding could be applied. And otherwise a pointer to a new expression tree
where:

- Subtrees with constant value are replaced with a corresponding unsigned
  literal node.
- Nodes where the operands can be swapped (i.e. nodes for multiplication and
  addition) have a constant right child node if at least one child node has a
  constant value.

In addition some special cases can be treated. For example, multiplication with
zero, multiplication with one, adding a zero, etc.

---- CODE (type=c) -------------------------------------------------------------
#ifndef ABC_EXPR_H
#define ABC_EXPR_H

// ...

// methods
bool isLValueExpr(const struct Expr *expr);
bool isConstExpr(const struct Expr *expr); // new

// ...

const struct Expr *constFoldExpr(const struct Expr *expr); // new

#endif // ABC_EXPR_H

--------------------------------------------------------------------------------

Changes to the Parser
=====================
The parser should call _constFoldExpr()_ before code generation. And of course
code should be generated for the optimized expression tree. It certainly would
be a nice feature if the generated Latex code contains the original tree and
if some optimization could be applied the folded tree.

Changes to _loadExpr()_
=======================
The implementation should use instructions with an immediate operand where
possible. Of course this requires another translation of enum constants.

---- CODE (type=c) -------------------------------------------------------------
// ...

static enum GenOp
makeOp3i(enum ExprKind kind)
{
    // ...
}

void
loadExpr(const struct Expr *expr, GenReg dest)
{
    // ...

    if (expr->kind >= EK_BINARY && expr->kind < EK_BINARY_END) {
	const struct Expr *left = expr->binary.left;
	const struct Expr *right = expr->binary.right;
	switch (expr->kind) {
	    case EK_ADD:
	    case EK_SUB:
	    case EK_MUL:
	    case EK_DIV:
	    case EK_MOD:
		{
		    loadExpr(left, dest);
		    if (isConstExpr(right)) {
			uint64_t rVal = right->primary.literal.uint;
			genOp3i(makeOp3i(expr->kind), rVal, dest, dest);
		    } else {
			GenReg tmp = genGetReg();
			loadExpr(right, tmp);
			genOp3r(makeOp3r(expr->kind), tmp, dest, dest);
			genUngetReg(tmp);
		    }
		}
		return;
	// ...
	}
    // ...
    }
    // ...
}
--------------------------------------------------------------------------------

Implementation Pattern
======================
It is convenient to have some helper functions for dealing with binary nodes
and unary nodes separately:

---- CODE (type=c) -------------------------------------------------------------
// stuff for constant folding

static const struct Expr *
constFoldBinary(const struct Expr *expr)
{
    assert(expr);
    assert(expr->kind >= EK_BINARY && expr->kind < EK_BINARY_END);

    // ...
}

static const struct Expr *
constFoldUnary(const struct Expr *expr)
{
    assert(expr);
    assert(expr->kind >= EK_UNARY && expr->kind < EK_UNARY_END);

    // ...
}

const struct Expr *
constFoldExpr(const struct Expr *expr)
{
    assert(expr);
    assert(expr->kind >= EK_BINARY && expr->kind < EK_PRIMARY_END);

    if (expr->kind >= EK_BINARY && expr->kind < EK_BINARY_END) {
	return constFoldBinary(expr);
    } else if (expr->kind >= EK_UNARY && expr->kind < EK_UNARY_END) {
	return constFoldUnary(expr);
    }
    return expr;
}
--------------------------------------------------------------------------------

Folding can be implemented recursively. For each non-primary node the following
is applied (in this order):

- All child nodes are replaced with folded nodes.
- If the left child node is constant and the right child node is not constant
  swap the child nodes if the operation allows that.
- If all child nodes are constant the node a new constant node gets created
  with the corresponding value.

In the end a pointer to the node gets returned. So this is either a pointer to
the original node or a new node.

Folding Binary Nodes
--------------------
Here almost the complete implementation of a function folding a binary node:

---- CODE (type=c) -------------------------------------------------------------
static const struct Expr *
constFoldBinary(const struct Expr *expr)
{
    // ...

    // const fold child nodes
    const struct Expr *left = constFoldExpr(expr->binary.left);
    const struct Expr *right = constFoldExpr(expr->binary.right);

    // handle all cases where folding is not possible
    if (isConstExpr(left) && !isConstExpr(right)) {
	// swap operands if possible
	switch (expr->kind) {
	    case EK_ADD:
	    case EK_MUL:
		return newBinaryExpr(expr->kind, right, left);
	    default:
		;
	}
    }
    if (!isConstExpr(left) || !isConstExpr(right)) {
	// nothing more can be done
	if (left == expr->binary.left && right == expr->binary.right) {
	    return expr;
	}
	return newBinaryExpr(expr->kind, left, right);
    }
    // otherwise return folded expression node
    // NOTE: here we exploit that in our case constants are always unsigned
    uint64_t leftVal = left->primary.literal.uint;
    uint64_t rightVal = right->primary.literal.uint;
    switch (expr->kind) {
	case EK_ADD:
	    return newUnsignedLiteralExpr(leftVal + rightVal);

	// TODO: handle other cases ...

	case EK_ASSIGN:
	default:
	    assert(0); // internal error
	    return 0; // prevent warning (never reached in debug mode)
    }
}


--------------------------------------------------------------------------------


Folding Unary Nodes
-------------------
Here almost the complete implementation of a function folding an unary node:

---- CODE (type=c) -------------------------------------------------------------
static const struct Expr *
constFoldUnary(const struct Expr *expr)
{
    assert(expr);
    assert(expr->kind >= EK_UNARY && expr->kind < EK_UNARY_END);

    // const fold child node
    const struct Expr *unary = constFoldExpr(expr->unary);

    // handle all cases where folding is not possible
    if (!isConstExpr(unary)) {
	if (unary == expr->unary) {
	    return expr;
	}
	return newUnaryExpr(expr->kind, unary);
    }
    // otherwise return folded expression node
    // NOTE: here we exploit that in our case constants are always unsigned
    switch (expr->kind) {
	case EK_UNARY_PLUS:
	    return unary;
	case EK_UNARY_MINUS:
	    return newUnsignedLiteralExpr(-unary->primary.literal.uint);
	default:
	    assert(0); // internal error
	    return 0; // prevent warning (never reached in debug mode)
    }
}
--------------------------------------------------------------------------------