CPE Part 14: Constant Folding

Example for Constant Folding

Here a simple example where constant folding can be applied:

session23/git/abc/examples/fold_example.abc 
x = 42;
y = 7 * -3 * -2 + x;
y = (1 + 1) * (1 + 1) - x;
y = x / 4 * 4;
y = x * 4 / 4;
y = x * (4 / 4);
y = x * (4 - 4);
y = x + (4 - 4);
y = x + (5 - 5);
y = x / 1;
y = x % 1;

theon$ ./xtest_abc fold_example.s fold_example.tex < examples/fold_example.abc
theon$ 

How constant folding was applied can be seen in the generated 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// ...

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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)
    }
}