Skip to content

Add an optional common subexpression elimination pass - #2483

Open
SahilRajputdotexe wants to merge 1 commit into
serge-sans-paille:masterfrom
SahilRajputdotexe:feat/common-subexpression-elimination
Open

SahilRajputdotexe wants to merge 1 commit into
serge-sans-paille:masterfrom
SahilRajputdotexe:feat/common-subexpression-elimination

Conversation

@SahilRajputdotexe

Copy link
Copy Markdown

This adds pythran.optimizations.CommonSubexpressionElimination, an optional pass that evaluates a repeated pure expression once into a __cse<N> local and rewrites every occurrence to read it.

Pythran already has the purity (PureExpressions) and use-def information needed to tell when two expressions are the same value, which the C++ compiler cannot recover from the generated templates.

Example, with pythran -P -pCommonSubexpressionElimination:

def f(a, b, c):
    return (a + b) * c + (a + b) * (c - 1.)

becomes

def f(a, b, c):
    __cse0 = (a + b)
    return ((__cse0 * c) + (__cse0 * (c - 1.0)))

It is conservative. Subscripts, container literals, comprehensions, lambdas, yield/await, starred, f-string parts and walrus are never hoisted, and neither are names, constants or attribute chains. Occurrences must resolve every name to the same definitions and sit in the same statement list, and a rebinding of an operand between them, or an OpenMP directive, blocks the rewrite. Short-circuit and other conditional contexts are left alone: operands of and/or after the first, later comparators of a chained comparison, branches of a conditional expression, assert messages and comprehension bodies. Overlapping groups hoist the larger one first, and the inner one is picked up on a later iteration of the pipeline.

I did not add it to the default optimizations list in pythran.cfg, since I could not judge the effect on compile time and generated code across the whole suite. It is reachable through -p or a custom optimizations entry. Happy to enable it by default if you prefer.

The grouping lives in a new RepeatedExpressions analysis. Tests are in test_optimizations.py: check_ast comparisons, plus checks that optimized functions return or raise exactly what the originals do (for example x and 1/x ... with x == 0). They only exercise the Python side. I ran them locally, and the full CI runs on my fork.

Pure expressions computed two or more times in the same statement list are
evaluated once into a __cse<N> local. The pass is not part of the default
optimization chain and can be enabled with -pCommonSubexpressionElimination.
@serge-sans-paille

Copy link
Copy Markdown
Owner

Thanks for the contribution. Please activate this pass and report compilation time impact on files from pythran/test/cases so that we see if it makes sense to let it in - I haven't reviewed the code but I'm not opposed to having it in, but as it require me too 'absorbe' it mentally, this may require some rewrite, if you're fine with it.

@serge-sans-paille

Copy link
Copy Markdown
Owner

(stated otherwise, there is no use of having it if it's not on by default)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants