Implementing common subexpression elimination

I am looking into implementing common subexpression elimination (CSE) for expression graphs corresponding to large mathematical expressions (millions of nodes).

What algorithms are suitable for performing this? I was searching the internet for an easy-to-implement algorithm but I could not find anything. If possible the algorithm should have a linear complexity in the number of nodes of the complete expression graph.

1

Best Answer

These are expressions with no side effects? Then the easiest thing to do is to hash the trees for each sub-expression into buckets to determine candidates for sub-expression elimination.This is a special case of CSE where all the expressions are in a single (huge) "basic block". (I use this idea as the basis for detecting duplicate code.)

If the expressions have order and side effects, you may want to consider Value Numbering.

Random Posts

Transform JSX to JS using babelUndo git stash pop that results in merge conflictHow to print the result of a function in C?Pytorch: Understand how nn.Module class internally workHow to get Maven report in html format?Switching between FIPS and Standard AWS EndpointsLoad yaml config with array typeProgrammatically darken a Hex colour [closed]Difference between -n and -np when running MPI script?Appending an id to a list if not already present in the listMakefile: Calling a recipe within another recipe will not run-dry itTailwindCss Fixed NavBarWhat is the use of EDI - Gentran ? What is called mapping in Gentran?Disable Button in Angular 2Advantages of stateless programming?Does the unary + operator have any practical use?Trying to put working arcpy.SearchCursor code into a functionRails memory leak: controller class holding a reference to instanceHow Could I Write a helper function which is query from mongodb , and then can call this func for any ejs templateDoes NPM ignore files listed in .gitignore?