Common Subexpression Elimination

Common Subexpression Elimination

Common subexpression elimination (CSE) is avoiding the recomputation of the same expression twice. There are many cases where the same computation appears multiple times in a single expression, or across the control flow of a program. Compiler optimizers attempt to automatically detect such cases and reuse the first computation.

In a complicated expression, there are often repeated sub-expressions. These are inefficient as they require the computer to calculate the same value twice or more. To save time, calculate the sub-expression first and store it in a temporary variable. Then replace the sub-expression with the temporary variable. For example:

    x = (i * i) + (i * i);

With a temporary variable, this becomes:

    temp = i * i;
    x = temp + temp;

Note that this attempt to be concise is incorrect:

    x = (temp = i * i) + temp; // Bug

This may fail because of its reliance on the order of evaluation of the + operator. It is not actually guaranteed in C++ that the + operator is evaluated left-to-right.

Common sub-expressions do not occur only in single expressions. It often happens that a program computes the same thing in subsequent statements. For example, consider the code sequence:

    if (x > y && x > 10) {
        // ...
    }
    if (x > y && y > 10) {
        // ...
    }

The Boolean condition “x>y” need be calculated only once:

    temp = (x > y);
    if (temp && x>10) {
        // ...
    }
    if (temp && y>10) {
        // ...
    }

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++