3 ms·
FTA: “Because optimizations run on an E-graph only add information in the form of new annotations, the order of the optimizations does not change the result. As
by Someone 3y ago
FTA: “Because optimizations run on an E-graph only add information in the form of new annotations, the order of the optimizations does not change the result. As long as the compiler continues running optimizations until they no longer have any new matches (a process known as equality saturation), the E-graph will contain the representation that would have been produced by the optimal ordering of an equivalent sequence of traditional optimization passes […] In practice, Cranelift sets a limit on how many operations are performed on the graph to prevent it from becoming too large.”
So, in practice, the order of optimizations can change the result? How easy is it to hit that limit?
- HelloNurse 3y agoFor example, simplification of arithmetic expressions and propagating constants need to be combined (discovery of constants can allow further simplification, simplification can reach constant results). With destructive updates you have to decide what variant has the last word (e.g. 2*a or a+a or a<<1), while an equality graph collects progress without heuristic and imprecise choices allowing equality saturation,