Description
EquivalentExpressions maintains a map of equivalent expressions. It is HashMap now so the insertion order is not guaranteed to be preserved later. Subexpression elimination relies on retrieving subexpressions from the map. If there is child-parent relationships among the subexpressions, we want the child expressions come first than parent expressions, so we can replace child expressions in parent expressions with subexpression evaluation.
For example, we have two different expressions Add(Literal(1), Literal(2)) and Add(Literal(3), add).
Case 1: child subexpr comes first. Replacing HashMap with LinkedHashMap can deal with it.
addExprTree(add)
addExprTree(Add(Literal(3), add))
addExprTree(Add(Literal(3), add))
Case 2: parent subexpr comes first. For this case, we need to sort equivalent expressions.
addExprTree(Add(Literal(3), add)) => We add `Add(Literal(3), add)` into the map first, then add `add` into the map
addExprTree(add)
addExprTree(Add(Literal(3), add))