Enhancing Compiler Optimization Efficiency through Grammatical Decompositions of Control-Flow Graphs

This thesis addresses the complexities of compiler optimizations, such as register allocation and Lifetime-optimal Speculative Partial Redundancy Elimination (LOSPRE), which are often handled using tree decomposition algorithms. However, these methods frequently overlook important sparsity aspects of Control Flow Graphs (CFGs) and result in high computational costs. We introduce the SPL (Series-Parallel-Loop) decomposition, a novel framework that offers optimal solutions to these challenges. A key contribution is the formulation of a general solution for Partial Constraint Satisfaction Problems (PCSPs) within graph structures, applied to three optimization problems. First, SPL decomposition enhances register allocation by accurately modeling variable interference graphs, leading to efficient register assignments and improved performance across benchmarks. Second, it optimizes LOSPRE by effectively identifying and eliminating redundancies in program execution. Finally, the thesis focuses on optimizing the placement of bank selection instructions to enhance data retrieval efficiency and reduce latency. Extensive experimentation demonstrates significant performance improvements over existing methods, establishing SPL decomposition as a powerful tool for complex compiler optimizations, including register allocation, LOSPRE, and bank selection.