Better Loop Fusion for LMS
This is my master thesis done at PPL in Stanford under the supervision of Prof. Kunle Olukotun. It improved LMS, a framework for embedding DSLs (domain-specific languages) into Scala which features many general optimizations that can be used by any DSLs for free. I implemented a more powerful and cleaner version of the loop fusion optimization from the compiler world. Loop fusion is an important performance optimization for all languages that feature list comprehensions and translate their high-level operations into loop-based representations. It can decrease runtime, memory footprint and code size through two different fusion cases: The simpler one is called horizontal or side-by-side fusion and fuses adjacent loops iterating over the same range, enabling further optimizations. The second one is vertical or pipeline fusion, where a producer and a consumer of data are fused, removing the need for the intermediate data structure.